【知识点】欧几里得算法求最大公约数

最大公约数

所为的最大公约数，是指两个或多个整数共有的约数中最大的那个数。换句话说，它是能同时整除给定的整数的最大整数。

例如，对于整数 \(12\) 和 \(18\)，它们的公约数有 \(1、2、3、6\)，其中最大的公约数为6，因此它们的最大公约数为 \(6\)。最大公约数通常用符号 \(\gcd(a, b)\) 来表示，其中 \(a\) 和 \(b\) 是要找到最大公约数的两个整数。

最大公约数的应用范围非常的广泛，我们常见的加密算法、分数的简化、时间频率的调整都离不开计算两个数的最大公约数。

普通算法求解最大公约数

对于求两个较小的数字的最大公约数，一个非常简单的方法就是遍历所有小于这两个数字的数字，并通过枚举的方法求出所有因数中最大的那一个因数。

具体代码如下：

int gcd(int a, int b) {
    // 初始化最大公约数为1，因为1是所有整数的公约数
    int result = 1; 
    for (int i = 2; i <= a && i <= b; ++i) {
        if (a % i == 0 && b % i == 0) {
            // 更新最大公约数
            result = i; 
        }
    }
    return result;
}

这种方法固然简便，但是速度比较慢。若给定的两个数字都是质数，那么这两个数的最大公因数都是 \(1\)，就算是经过枚举优化的代码时间复杂度也是 \(O(n)\) 级别的。

显然我们需要找到一个更优的算法来解决寻找最大公因数问题的解。

欧几里得算法

早在古希腊时期，著名几何学之父欧几里得就在他的作品中提到过 GCD 算法。在计算机史上，这可以称之为是世界上第一个"算法"，算法的概念也就从此诞生了。

欧几里得算法的内容就是快速求出两个数字 \(A, B\) 的最大公因数。具体地，欧几里得算法如下，其中 \(A \space \text{mod} \space B\) 表示 \(A \div B\) 的余数：

再根据余数的基本性质：

1. \(\gcd(A, 0) = 0\)
2. \(\gcd(0, B) = 0\)

这样子就可以通过递归的方式快速求的 \(\gcd(A, B)\) 的值（显然，这个递归版本的代码竟然比暴力计算 GCD 的代码更佳清爽和简洁）：

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

欧几里得算法的证明

首先要证明递归的有穷性，即证明算法会在有限步骤内结束。在递归的过程中，每一步两个参数的值都会减少。而在有限的步数内，被除数必然会等于 \(0\)，因为每一步的被除数都是上一层递归的除数，而除数在每一步都变为上一步的余数，余数必然小于除数，因此被除数在每一步都会减小。由于被除数是一个非负整数，所以它必然会在有限步骤内变为 \(0\)，因此算法必然会终止，不会无限递归下去。

众所周知，无法证明正确性的算法不是好算法（事实上，算法的五大要素之一就是正确性）。尽管欧几里得算法有许多证明方法，但这里就提供一个最好理解的（归纳法）。

欧几里得算法的正确性来源于数学上的一个基本事实：如果一个数能同时整除两个数，那么它也能整除它们的差。 例如数字 \(5\)，它可以整除 \(15\) 和 \(20\)，那么它一定可以整除这两个数的差 \(\lvert15, 20\rvert = 5\)。

因此，如果两个整数的最大公约数是 \(d\)，那么它们可以表示为 \(a = md\) 和 \(b = nd\)，其中 \(m\) 和 \(n\) 是整数，而 \(d\) 是最大公约数。那么 \(a - b = (m - n) \cdot d\)，即 \(a\) 和 \(b\) 的差是 \(d\) 的倍数。所以 \(d\) 同时是 \(a\) 和 \(b\) 的公约数。

到此为止，有关欧几里得算法的内容全部结束了。本文后续将会更新一些有关 GCD 算法的一些实际应用。

相关链接引用

Khan Academy - The Euclidean Algorithm。