方法一:枚举:1、设t为2;
2、如果u和v都能被t整除,则记下这个t
3、t加1后重复第2步,直到t等于u和v;
4、那么,曾经记下的最大的可以同时整除u和v的t就是gcd(最大公约数)
方法二:辗转相除法:1、如果b等于0,计算结束,a就是最大公约数;
2、否则,计算a除以b的余数,让a等于b,而b等于那个余数;
3、回到第一步。
比如说令a=12,b=18,t为a%b
a b t
12 18 12
18 12 6
12 6 0
6 0
代码如下:
#include <stdio.h>
int main()
{
int a,b;
int t;
scanf("%d %d", &a, &b);
while ( b != 0 ) {
t = a%b;
a = b;
b = t;
}
printf("最大公约数是%d\n",a);
return 0;
}
|