辗除法？

haiouda

1. #include <stdio.h>
   
2. 
   
3. void main()
   
4. {
   
5.         int a,b,i,gab;        // yab 为a、b 的公约数,gab为a、b的最小公倍数
   
6.         printf("请输入两个整数:");
   
7.         scanf("%d %d",&a,&b);
   
8.         
   
9. 
   
10.         for (i=(a>b?a:b);i<=a*b;i++)
    
11.         {
    
12.                 if(i%a==0 && i%b==0)
    
13.                 {
    
14.                         gab=i;
    
15.                     break;
    
16.                 }
    
17. 
    
18.         }
    
19. printf("%d和%d的最大公约数是：%d\n",a,b,a*b/gab); // yab== a*b/gab
    
20. printf("%d和%d的最小公倍数是：%d\n",a,b,gab);
    
21. }

复制代码

C 100题之16 求最大公约数和最小公倍数.
一、如下图，辗除法？？？没看明白，请教下， 谢谢。
二、上面代码是我编的，请问二个方法哪个速度更快？

张林要努力啊

网上找的：

设两数为a、b(b<a)，求它们最大公约数(a、b)的步骤如下:用a/b，得a/b=q......r1(0≤r)。若r1=0，则(a，b)=b;若r1≠0，则再用b/r1，得b/r1=q......r2 (0≤r2).若r2=0，则(a，b)=r1，若r2≠0，则继续用r1/r2,……如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。