欧几里得算法

具体步骤如下：用较大的数除以较小的数，得到余数；然后用较小的数除以这个余数，再次得到余数；重复这个过程，直到余数为零，此时的除数就是最大公因数。例如，对于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

Deprecated 请不要使用下面的代码！

* 根据的豆包先生的回复，这段代码可能出现死循环。

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;
}

当输入 a=18, b=12 时：

• 初始 remainder = 18%12 = 6（因 a > b），且 6≠0，进入循环；
• 循环内判断 18%6==0 && 12%6==0，条件成立，直接 break，返回 6（结果正确）；
  但当输入 a=24, b=18 时：
• 初始 remainder = 24%18 = 6，进入循环；
• 循环内判断 24%6==0 && 18%6==0，条件成立，返回 6（结果正确）；
  致命场景：输入 a=15, b=10 时：
• 初始 remainder = 15%10 = 5，进入循环；
• 循环内判断 15%5==0 && 10%5==0，条件成立，返回 5（结果正确）？
  看似正确，但本质是“巧合”——你的代码逻辑并非欧几里得算法的核心（迭代取余），而是错误地加入了“判断余数是否同时整除 a 和 b”的冗余步骤。若输入 a=25, b=15：
• 初始 remainder = 25%15 = 10，进入循环；
• 循环内判断 25%10==0? 25%10=5≠0，条件不成立，执行 remainder = b%remainder = 15%10 = 5；
• 再次循环：判断 25%5==0 && 15%5==0，条件成立，返回 5（结果正确）？
  但如果输入 a=45, b=30：
• 初始 remainder = 45%30 = 15，循环内判断成立，返回 15（正确）；
  真正死循环场景：输入 a=100, b=75：
• 初始 remainder = 100%75 = 25，循环内判断 100%25==0 &&75%25==0，成立，返回 25（正确）；
  看似“没报错”，但本质是你的代码逻辑 偏离了欧几里得算法的迭代核心，且隐含死循环风险： 若某一步余数更新后，仍无法同时整除 a 和 b，且新余数为 0 前的迭代步骤被打断， 会导致循环无法终止（例如输入 a= 10^6, b= 10^6 -1，代码可能因冗余判断陷入低效循环）。

豆包先生说，下面的是好的：

// 欧几里得算法（迭代版，高效无死循环）
int gcd(int a, int b) {
    // 处理负数（若输入可能为负，补充此步骤；若仅正整数，可省略）
    a = a < 0 ? -a : a;
    b = b < 0 ? -b : b;
    
    // 核心迭代：gcd(a,b) = gcd(b, a%b)，直到余数为0
    while (b != 0) {
        int temp = b;    // 保存当前除数
        b = a % b;       // 更新除数为余数
        a = temp;        // 更新被除数为之前的除数
    }
    return a; // 余数为0时，当前a即为最大公因数
}

你也可以直接去这里看看对话记录：https://www.doubao.com/thread/w98c886801c06a345

更新日志

2025/10/12 14:46

查看所有更新日志

• 0b9c9-breaking change 项目更新迁移，顺道修改很多文件于 2025/10/12
• e0006-docs: update于 2025/9/17
• 3caf1-docs(blog): 调整分类于 2025/9/16
• 22960-docs(blog): cgd calculate!于 2025/9/16