辗转相除法求最大公约数和最小公倍数
发布时间：2010/7/5 15:35:47 来源：城市学习网 编辑：ziteng
1: /*辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。
2: 例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；
3: 因为252 ? 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩
4: 小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的
5: 还没有变成零的数就是两数的最大公约数。
6: */
7: #include <stdio.h>
8:
9: int getGCDAndLCM(int a,int b){
10: int max=a>b?a:b;//将较大的数赋给max
11: int min=(max=a)?b:a;//将较小的数赋给min
12: int temp;//暂时存储变量
13: while(max!=0){
14: temp=min%max;
15: min=max;
16: max=temp;
17: }
18: printf("最大公约数为%d\n",min);
19: printf("最小公倍数为%d\n",a*b/min);
20: }
21:
22: int main(){
23: printf("输入两个数整数值\n");
24: int a,b;
25: scanf("%d",&a);
26: scanf("%d",&b);
27: getGCDAndLCM(a,b);
28: return 0;
29: }
