欧几里得算法

具体步骤如下：用较大的数除以较小的数，得到余数；然后用较小的数除以这个余数，再次得到余数；重复这个过程，直到余数为零，此时的除数就是最大公因数。例如，对于24和36，用36除以24余12，再用24除以12余0，所以12就是它们的最大公因数。

尝试证明（并不严谨）

余数：

$$a = kb + r$$

其中 $r$ 即为余数，并且有 $r < b, \space r \ge 0$.

不妨假设, $\mathrm{gcd(}a,\space b \mathrm{)}$ (a, b 的最大公因数) 等于 $d$ .

那么, 容易得到， $a = \alpha d$ ， $b = \beta d$，其中 $\alpha$ , $\beta$ 是两个整数.

把这俩等式代入 $a = kb + r$ , 我们得到：

$$\alpha d = k \beta d + r$$

移项并整理, 不难发现:

$$r = (\alpha - k \beta)d$$

由于 $\alpha$ , $\beta$ 和 $k$ 都是整数, 所以经过加减乘三种运算后得到的数仍然是整数, 所以 $r$ 是 a, b 最大公因数的倍数. 也就是说, $d$ 也是 $r$ 的因数.

所以, 接下来只需要求 $\mathrm{gcd(}r,\space b \mathrm{)}$ 就可以了!

那么, 如何求 $\mathrm{gcd(}r,\space b \mathrm{)}$ ? 只需要把 $b$, $r$ 继续进行取余的操作(也就是把$b$, $r$ 当作 $a$, $b$ 进行迭代)

于是, 就得到了上面的算法.

代码实现

C Language

int gcd(int a, int b);
int gcd(int a, int b)
{
    int remainder = a < b ? b % a : a % b;
    if (remainder == 0) {
        return a < b ? a : b;
    }
    while (1)
    {
        if (a % remainder == 0 && b % remainder == 0)
            break;
        remainder = a < b ? a % remainder : b % remainder;
    }
    return remainder;
}

更新日志

2025/9/16 13:41

查看所有更新日志

• 3caf1-docs(blog): 调整分类于 2025/9/16