最大公约数

1、枚举

 1 #include <stdio.h>
 2 
 3 int main()
 4 {
 5     int a, b;
 6     int min;
 7 
 8     scanf_s("%d %d", &a, &b);
 9     if (a < b)
10     {
11         min = a;
12     }
13     else
14     {
15         min = b;
16     }
17     
18     int ret = 0;
19     for (int i = 1; i <= min; i++)
20     {
21         if (a % i == 0)
22         {
23             if (b % i == 0)
24             {
25                 ret = i;
26             }
27         }
28     }
29     
30     printf("%d和%d的最大公约数是%d.
", a, b, ret);
31 
32     return 0;
33 }

1、辗转相除法

 1 /* 
 2     如果b等于0，计算结果，a就是最大公约数；
 3     否则，计算a除以b的余数，让a等于b，而b等于那个余数；
 4     回到第一步。
 5 
 6     a    b    temp
 7     12    18    12
 8     18    12    6
 9     12    6    0
10     6    0
11 */
12 #include <stdio.h>
13 
14 int main()
15 {
16     int a, b;
17     int temp;
18 
19     scanf_s("%d %d", &a, &b);
20     
21     while (b!=0)
22     {
23         temp = a % b;
24         a = b;
25         b = temp;
26     }
27 
28     printf("gcd = %d
", a);
29     return 0;
30 }