【手撕代码3】-求两个数的最大公约数/最小公倍数

求最大公约数

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 //枚举法
 6 void find1(int a,int b)
 7 {
 8     int i = min(a, b);
 9     for (; i >= 1; i--)
10     {
11         if (a % i == 0 && b % i == 0)
12         {
13             cout << i << endl;
14             break;
15         }
16     }
17     return;
18 }
19 //辗转相除法
20 void find2(int a,int b)
21 {
22     int t;
23     if (b > a) { t = a; a = b; b = t; }
24     while (a % b != 0)
25     {
26         t = a % b;
27         a = b; b = t;
28     }
29     cout << b << endl;
30     return;
31 }
32 
33 int main()
34 {
35     int a, b;
36     cin >> a >> b;
37     find1(a, b);
38     find2(a, b);
39     return 0;
40 }

最小公倍数=两个整数之积/最大公约数

我们知道几个数的最小公倍数是把相等的公因数只乘一遍.
两个整数之积把最大公约数多乘了一遍,然后再除去就是最小公倍数了.
如：24,36的最大公约数是12=2*2*3
最小公倍数是：2*2*3*2*3
面它们两个的积为：2*2*2*3*2*2*3*3=[（2*2*3）^2]*2*3

原理来自 https://www.zybang.com/question/2ac105bdbc8b807c5bfbafc98fe2512b.html