解题思路:
辗转相除法:辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。
例如,求(3,2):
∵ 3÷2=1(余1 !0)
∴(3,2)=(2,1);
∵ 2÷1=2(余0)
∴ (2,1)= 1;
∴ (3,2)=1。
可以写成右边的格式。
用辗转相除法求几个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。最后所得的那个最大公约数,就是所有这些数的最大公约数。
参考代码:
#include<stdio.h>
int fun(int a,int b){ //计算最大公约数
if(a % b ==0) //判断余数是否为0,若为0,则b是二者的最小公约数
return b;
else
fun(b, a % b); //否则,递归
}
int main()
{
int a,b,c,num1,num2;
scanf("%d %d", &a, &b);
if (a < b){ //保证a,b的大小顺序
c=a;
a=b;
b=c;
}
num1=fun(a,b); //计算最大公约数
num2=a*b/num1; //计算最小公倍数
printf("%d\n%d",num1,num2);
return 0;
}
0.0分
1 人评分