看书的时候，我看到了关于求最大公约数的算法，不妨就做个笔记。

最大公约数 Greatest Common Divisor

求最大公约数有多种方法，如质数分解法、短除法、辗转相除法（欧几里德算法）和更相减损法等。

质数分解法

质数分解法是小学学过的第一种求最大公约数的算法（那个时候还没有算法的概念）。就是求出两个数各自的质数，然后求共有的质数的乘积。

短除法

短除法本质上也是质数分解法，使用短除号来计算。

更相减损法

更相减损法出自刘徽的《九章算术》：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

计算步骤： 1. 任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 2. 以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

辗转相除法（欧几里德算法）

我在学习编程的时候，看到的就是这个算法。具体就是：对任意 m, n 属于 N, 有 gcd(m, n) = gcd(n, m mod n)。这个方法可以很好通过递归实现。

证明：

设 k 为 a, b 的公约数, 即有 a = pk, b = qk 其中 a, b 均为自然数, 另 p, q, x, y 为任意整数.

有 xa + yb = xpk + yqk = (xp + yq)k.

那么, 我们可以令 m = ha + b, n = a, m mod n = b 所以, h 为任意整数 k 就是 m, n 的公约数.

接着证明 k 为最大公约数, 令 gcd() 为求最大公约数.

令 k = gcd(m, n), j = gcd(n, m mod n), 其中 m = hn + b.

由于 m = hn + (m mod n), j 是 n 和 (m mod n) 的最大公约数，所以 j 也是 m 和 n 的公约数.

又由于 k 为 m 和 n 的最大公约数, 所以, k >= j.

又有 (m mod n) = m - hn, k 是 m 和 n 的最大公约数, 所以 k 也是 (m mod n) 和 n 的公约数.

又由于 j 为 (m mod n) 和 n 的最大公约数, 所以, j >= k.

因为 k >= j, j >= k, 所以 k = j.

由此得证.

可以通过 C++ 来实现：

#include <iostream>
int gcd(int a,int b)
{
    return a%b ? gcd(b,a%b) : b;
}
int main()
{
    int x, y;
    cin >> x, y
    cout << gcd(x, y);
    return 0;
}

最小公倍数 Lowest Common Multiple

当有了最大公约数就好求最小公倍数了。若以 (a,b) 来记 a 和 b 的最大公约数，以 [a,b] 来记 a 和 b 的最小公倍数，那么有 (a, b)[a, b] = ab。所以，只需要用 a 和 b 的乘积除以 a 和 b 的最大公约数就可以了。