最大公约数与欧几里得算法

Published: Thu Feb 19 2026 | Modified: Sat Feb 07 2026 , 3 minutes reading.

GCD 与欧几里得：伟大的协调者

算法背后的故事：地砖的逻辑

想象你有一块宽 252 单位、长 105 单位的地面。你想用尽可能大的正方形地砖铺满这块地，且不需要切割任何地砖。

这就是在寻找 最大公约数 (GCD)。

公元前 300 年，亚历山大的 欧几里得 (Euclid) 写下了一个简单但深刻的观察：

“如果一个正方形能完美契合两个不同的长度，那么它也一定能完美契合它们的差值。”

如果你有一个 252x105 的地面，你不可能放入比 105 更大的正方形。于是你从 252 中减去 105，剩下 147。再减去 105，剩下 42。现在你试图将 42 放入 105 中……

通过不断地相减（或者使用除法的余数），数字不断缩小，直到它们相遇在一个完美的值。对于 252 和 105，这个值就是 21。

为什么需要它？

分数简化： 你的计算器如何将 42/105 变成 2/5？它找到了 GCD (21) 并同时除以它。
宽高比： 将屏幕分辨率如 1920x1080 转化为 16:9 的比例，需要用到 GCD (120)。
密码学： 许多加密算法（如 RSA）要求数字是“互质”的（即 GCD 为 1），以确保数学逻辑能正确运行。
同步： 寻找两个事件的“最小公倍数 (LCM)”依赖于它们的 GCD ( $LCM(a,b) = (a \times b) / GCD(a,b)$ )。

算法是如何“思考”的

这个算法是一个递归缩小者。

取模之舞： 与其从 $A$ 中减去多次 $B$ ，我们直接取余数： $A \pmod B$ 。
接力： 问题转化为：“寻找 $B$ 和 $A \pmod B$ 的最大公约数。”
终点： 当余数为 0 时，当前的 $B$ 就是我们要寻找的那个“共同节奏”。

工程决策：二进制 GCD

虽然标准的欧几里得算法已经非常快 ( $O(\log N)$ )，但现代 CPU 有时会使用 二进制 GCD (Stein 算法)。

它避开了昂贵的“除法/取模”运算。
它只使用“位移”和“减法”。
它就像是专为底层硬件性能打造的赛车。

实现参考 (Python)

def gcd(a, b):
    # 欧几里得智慧的优雅迭代版
    while b:
        # a 除以 b 的余数
        a, b = b, a % b
    return a

def lcm(a, b):
    # 同步依赖于和谐
    if a == 0 or b == 0: return 0
    return abs(a * b) // gcd(a, b)

# 示例
print(f"252 和 105 的 GCD: {gcd(252, 105)}") # 21
print(f"1920x1080 的宽高比: {1920//gcd(1920, 1080)}:{1080//gcd(1920, 1080)}") # 16:9

小结

欧几里得算法教会我们：寻找和谐，必须减少摩擦。通过除法剥离多余的部分，我们揭示了连接两个不同数字的共同纽带。它提醒我们，即使在最复杂的系统中，核心通常也存在一个简单且共享的真理单位。

Luke Sun