求两个数的最大公约数
问题分析
设有a,b两个正整数,求a,b的最大公约数。
算法分析
辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。
例如
a=24 b=18
24/18 = 1 余数 6
18/6 = 0 余数 0
最大公约数 6//即余数为零时的除数
除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数
代码实现
#include <stdio.h>
int main()
{
int a, b,c;
scanf("%d %d", &a, &b);
c = a % b;
while (c != 0)
{
a = b;
b = c;
c = a % b;
}
printf("%d", b);
}
return 0;
}
注意事项
可能有人会问是否需要判断两数的大小关系
答案为不用
如果a<b
a<b
a%b = 0 a
将变成
b%a