欧几里得算法

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

欧几里得算法（GCD）

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

欧几里得算法的基本原理用一句话就可以说清楚： 两个整数的最大公约数等于其中较小的数和两数的差的最大公约数，即 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);