用尺子量布找最大公约数——辗转相除法（欧几里得算法）详解

你遇到过这样的问题吗？要把12块巧克力和18块糖果分给一些小朋友，每个小朋友分到的巧克力数量相同，糖果数量也相同，且不能有剩余。那么最多可以分给几个小朋友呢？答案就是12和18的最大公约数——6。求最大公约数有很多方法，其中有一种特别巧妙的方法叫做辗转相除法（也叫欧几里得算法），它就像用一把长尺子去量一块布，反复相除，直到量完为止。

什么是最大公约数？

两个整数共享的最大因数叫作最大公约数。比如12的因数有1,2,3,4,6,12；18的因数有1,2,3,6,9,18。它们共同的因数有1,2,3,6，其中最大的那个是6。所以12和18的最大公约数是6，记作 gcd(12,18) = 6。

辗转相除法的原理——像量布一样

古人想了一个很聪明的办法：不需要列出所有因数，就能快速找到最大公约数。

生活例子：假设你有两块布，一块长12厘米，一块长18厘米。你想用它们剪出最长的布条，使得布条能正好量完两块布。怎么做呢？

1. 用长的布（18厘米）去量短的布（12厘米）——量1次，剩下18-12=6厘米（余数6）。
2. 再用刚才的短布（12厘米）去量剩下的6厘米——正好量2次，余数为0。
3. 最后剩下的那段长度6厘米，就是两块布的最大公约数。

如果余数不为0，就一直重复：用上次的“短布”去量“剩下的布”，直到余数为0。最后那个非零的除数就是答案。

数学上：给定两个正整数 a 和 b（假设 a ≥ b），计算 a 除以 b 的余数 r = a % b。如果 r = 0，则 b 就是最大公约数；否则用 b 代替 a，用 r 代替 b，重复这个过程。

一步一步手算演示

我们用手算看一下 gcd(12, 18) 的过程（注意：一开始我们交换顺序让 a 是较大的数）：

• 步骤1：a = 18, b = 12，计算 18 ÷ 12 = 1 余 6 → 余数 r = 6，不为0，所以更新 a = 12, b = 6。
• 步骤2：a = 12, b = 6，计算 12 ÷ 6 = 2 余 0 → 余数 r = 0，循环结束，答案就是 b = 6。

所以最大公约数是6。

再试一个例子：gcd(100, 35)

• a = 100, b = 35，100 ÷ 35 = 2 余 30 → 余数30，更新 a=35, b=30
• a = 35, b = 30，35 ÷ 30 = 1 余 5 → 余数5，更新 a=30, b=5
• a = 30, b = 5，30 ÷ 5 = 6 余 0 → 余数为0，循环结束，答案是 b = 5。

所以 gcd(100,35) = 5。

Python代码实现

用Python写起来非常简洁，核心就是一个 while 循环：

def gcd(a, b):
    # 当 b 不为 0 时，反复用 a 除以 b，并把 (b, a%b) 作为新的 (a, b)
    while b != 0:
        a, b = b, a % b   # 同时赋值：新 a = 原来的 b，新 b = 原来的 a 除以 b 的余数
    return a               # 当 b 变成 0 时，a 就是最大公约数

# 测试
print(gcd(12, 18))   # 输出 6
print(gcd(100, 35))  # 输出 5

代码中的 a % b 就是取余数。比如求 gcd(12,18) 时，初始 a=12, b=18，但这里要注意：如果 a 比 b 小，第一次循环时会交换吗？我们来看：a=12, b=18，计算 12 % 18 = 12，所以新 a = 18, 新 b = 12。也就是说，即使你传参时 a 小于 b，第一轮循环也会自动交换，因为余数总是比除数小，而新的 a 变成了原来的 b，自然就保证了大数在前。所以这个代码对任何正整数都适用。

算法为什么这么快？

辗转相除法每次迭代都会让两个数至少减小一半（因为余数小于除数，而且每次循环数字迅速变小）。对于两个很大的数，比如 123456789 和 987654321，最多只需要几十次循环就能出结果。相比列举所有因数的方法（要试除很多次），它快得多。所以计算机科学中很多地方都用它，比如密码学中的 RSA 算法也依赖于求最大公约数。

新手容易犯的错误

错误1：忘记处理 a 小于 b 的情况

有的同学会先写 if a < b: a,b = b,a 来保证 a 较大。其实不需要，因为上面代码中第一轮循环会自动处理。但如果你写错了循环条件，比如 while a != b 之类的，就可能陷入死循环。记住：条件永远是 while b != 0。

错误2：混淆取余和整除

a % b 是取余数，不是整除。有的同学会写成 a / b，那样得到小数，无法用于辗转相除。一定要用取余运算符 %。

错误3：忘记返回结果

循环结束后，最大公约数存在 a 中（因为最后 b=0，而 a 是上一轮的 b）。如果返回 b 就会得到0。所以记得 return a。

完整可运行的示例

下面是一个完整的程序，让用户输入两个整数，输出它们的最大公约数：

# 定义辗转相除法函数
def gcd(a, b):
    # 当 b 不为 0 时，反复用 a 除以 b，并把 (b, a%b) 作为新的 (a, b)
    while b != 0:
        a, b = b, a % b   # 同时赋值
    return a

# 获取用户输入
num1 = int(input("请输入第一个正整数："))   # 第一个数
num2 = int(input("请输入第二个正整数："))   # 第二个数

# 计算并输出结果
result = gcd(num1, num2)
print(f"{num1} 和 {num2} 的最大公约数是 {result}")

运行示例：

请输入第一个正整数：72
请输入第二个正整数：120
72 和 120 的最大公约数是 24

相关知识点指引

学会了辗转相除法，你还可以继续学习：

• 最小公倍数（LCM）：两个数的最小公倍数等于它们的乘积除以最大公约数，即 lcm(a, b) = a * b // gcd(a, b)。比如12和18的最小公倍数 = 12×18÷6 = 36。
• 扩展欧几里得算法：不仅能求最大公约数，还能找到整数 x、y 使得 ax + by = gcd(a,b)，这个在解不定方程和密码学中很有用。
• 分数化简：化简分数时，分子分母同除以它们的最大公约数，比如 18/24 化简为 3/4。
• 判断互质：如果两个数的最大公约数为1，则它们互质。例如8和15互质，因为 gcd(8,15)=1。

辗转相除法是数论中最基础也最重要的算法之一。它简单、快速、优雅，像一把万能尺子，帮你解决很多和“公因数”有关的问题。下次遇到分糖果、排队分组、简化分数，都可以试试它！