欧几里得算法

什么是欧几里得算法？欧几里得算法是为了解决 GCD 问题，这里的 GCD 是指 Greatest Common Divisor 即最大公约数，而不是 iOS 中的 Grand Central Dispatch 🤣 。所以这篇分享是关于算法的。

欧几里得算法（GCD）

求 GCD 在数论中公认的最常用算法即为欧几里得算法，也就是我们在高中时学到的辗转相除法。

欧几里得算法的基本原理用一句话就可以说清楚：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数，即 $gcd(a, b) = gcd(b, a\ mod\ b)$ 。

为什么可以这么求呢，这里可以简单证明一下：

假设 $$a, b (a > b)$$ 两个数的一个公约数是 $$t$$ ，则有

a=n\times t \\ b=m\times t

因为 $$a > b$$ ，设 $$a = k \times b + r$$ ，即 $r = a\ mod\ b$ ，将 $$a,b$$ 代入展开可得：

a = n \times t = k \times m \times t + r \\ \Rightarrow r = (n - k \times m) \times t

由于 $(n-k \times m) \times t$ 一定是整数，所以 a、b 的公约数 t 也是 r 的约数。所以如果我们递归的求解 $a\ mod\ b$ 也就是 a % b ，就可以得到 a、b 的最大公约数 GCD 了。什么时候递归结束呢？当 a % b == 0 的时候，因为在这个过程中，如果 a % b 无法求得正整数 r 时，则无法继续按照上述规律继续拆分。

# python
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

// C++
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

这里另外提一句，a、b 两数的最大公倍数 LCM(a, b) = a * b / GCD(a, b) 。这里就不证明了，有兴趣的自己谷歌。

本作品采用 知识署名-非商业性使用-禁止演绎（BY-NC-ND） 4.0 国际许可协议 进行许可。