C++欧几里得算法求最大公约数和最小公倍数

定义

最大公约数即为 Greatest Common Divisor，常缩写为 gcd。
一组整数的公约数，是指同时是这组数中每一个数的约数的数。
一组整数的最大公约数，是指所有公约数里面最大的一个。
那么如何求最大公约数呢？我们先考虑两个数的情况。

欧几里得算法

过程

如果我们已知两个数 (a) 和 (b)，如何求出二者的最大公约数呢？
不妨设(a > b)
我们发现如果 b 是 a 的约数，那么 b 就是二者的最大公约数。 下面讨论不能整除的情况，即(a = b * q + r),
其中(r < b)
我们通过证明可以得到(gcd(a, b) = gcd(b, amodb)),过程如下：
设 (a=bk+c)，显然有 (c=a bmod b)。设 (d mid a),(~d mid b)，则(c=a-bk), (frac{c}{d}=frac{a}{d}-frac{b}{d}k)。
由右边的式子可知(frac{c}{d}) 为整数，即 (d mid c)，所以对于 (a),(b) 的公约数，它也会是 (b),(a bmod b) 的公约数。
反过来也需要证明：
设 (d mid b),(~dmid (a bmod b))，我们还是可以像之前一样得到以下式子
(frac{abmod b}{d}=frac{a}{d}-frac{b}{d}k,~frac{abmod b}{d}+frac{b}{d}k=frac{a}{d})。
因为左边式子显然为整数，所以(frac{a}{d}) 也为整数，即 d mid a，所以 b,abmod b 的公约数也是 a,b 的公约数。
既然两式公约数都是相同的，那么最大公约数也会相同。
所以得到式子(gcd(a, b) = gcd(b, amodb))
既然得到了 (gcd(a, b) = gcd(b, r))，这里两个数的大小是不会增大的，那么我们也就得到了关于两个数的最大公约数的一个递归求法。

实现

int gcd(int a, int b) {     if(b == 0) return a;     return gcd(b, a % b); } 

最小公倍数

int gcd(int a, int b) {     if(b == 0) return a;     return gcd(b, a % b); } int lcm = a * b / gcd(a, b);