Algorithm Design——最大公约数、最小公倍数

最大公约数

 1 /**
 2 最大公约数（GCD，greatest common divisor），欧几里得算法啦~~
 3 */
 4 
 5 #include<cstdio>
 6 using namespace std;
 7 
 8 //递归形式
 9 /*int gcd(int a, int b)
10 {
11     if(b == 0)
12         return a;
13     else
14         return gcd(b, a % b);
15 }*/
16 
17 //非递归形式
18 int gcd(int a, int b)
19 {
20     while(b != 0)
21     {
22         int t = a % b;
23         a = b; 
24         b = t;
25     }
26 
27     return a;
28 }
29 
30 int main()
31 {
32     int a, b;
33     while(scanf_s("%d%d", &a, &b) != EOF)
34     {
35         printf_s("%d
", gcd(a, b));
36     }
37 }

最小公倍数算法

 1  /**
 2     a和b的最小公倍数  = a * b / gcd(a, b)
 3 */
 4 
 5 #include<cstdio>
 6 
 7 int gcd(int a, int b)
 8 {
 9     while(b != 0)
10     {
11         int t = a % b;
12         a = b;
13         b = t;
14     }
15 
16     return a;
17 }
18 int main()
19 {
20     int a, b;
21     while(scanf_s("%d%d", &a, &b) != EOF)
22     {
23         printf_s("%d
", a * b / gcd(a, b));
24     }
25     return 0;
26 }