最大公约数和最小公倍数

使用的辗转相除法

辗转相除法:辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法

例如,求(319,377):

∵ 319÷377=0(余319)

∴(319,377)=(377,319);

∵ 377÷319=1(余58)

∴(377,319)=(319,58);

∵ 319÷58=5(余29)

∴ (319,58)=(58,29);

∵ 58÷29=2(余0)

∴ (58,29)= 29;

∴ (319,377)=29。

可以写成右边的格式。

用辗转相除法求几个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。最后所得的那个最大公约数,就是所有这些数的最大公约数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
int main() {
int maxgongyue(int x,int y);
int mingongbei(int num,int finax);
int x,y,num;
printf("请输入俩个数:\n");
scanf("%d %d",&x,&y);
num=x*y;
printf("最大公约数是:%d\n",maxgongyue(x,y));
printf("最小公倍数是:%d\n",mingongbei(num,maxgongyue(x,y)));
return 0;
}

int maxgongyue(int x,int y){
int temp,yushu;
if(x<y) { //交换成大的在前,小的在后
temp=x;
x=y;
y=temp;
}
while(y!=0) { //辗转相除法,如果余数不为0,则循环
yushu=x%y; //求余数
x=y; //将小的赋值给大的
y=yushu; //将余数赋值给小的
}//一直除到余数为0时,这时候的x就是最大公约数
return(x);
}

int mingongbei(int num,int finax){
return(num/finax);
}
打赏了解一下?
0%