最大公约数（GCD）：公平分配的秘密武器

你有没有遇到过这样的场景：和好朋友一起分零食，既要分得公平，又要分的份数最多？比如一包12颗糖果和8块巧克力，想平均分成若干份，每份里的糖果数和巧克力数都相同，还不能有剩余。那么最多能分给几个人呢？答案就是求12和8的最大公约数（GCD，Greatest Common Divisor）。最大公约数就是两个数能同时整除的最大的那个数——就像两个人能一起公平分东西的最大份数。

什么是最大公约数？

两个数A和B的最大公约数，就是能同时整除A和B的所有正整数中最大的那个。比如说：

12的因数有：1, 2, 3, 4, 6, 12
8的因数有：1, 2, 4, 8
它们共同的因数（公约数）是1, 2, 4，其中最大的就是4。所以12和8的最大公约数是4。

生活例子：你想把18个本子和24支笔平均分给一些同学，每个同学拿到的本子数和笔数一样多，并且没有剩余。最多能分给几个同学？答案是求18和24的最大公约数，结果是6。也就是说，最多可以分给6个同学，每人拿3个本子和4支笔。

另一个例子：你有15颗糖，你的朋友有10颗糖，你们想合在一起重新分成相同的堆，每堆里两人的糖数比例不变，最多能分几堆？答案是5堆（15和10的最大公约数是5），每堆有3颗你的糖和2颗朋友的糖。

辗转相除法：古老又聪明的算法

求最大公约数有很多方法，比如列举因数法（把两个数的所有因数都列出来找共同的），但数字一大就不方便了。这里介绍一个两千多年前欧几里得发明的“辗转相除法”（也叫欧几里得算法）。它的核心思想是：

两个数的最大公约数等于其中较小的数和两数相除的余数的最大公约数。

用公式表示就是：gcd(a, b) = gcd(b, a % b)，一直重复这个操作，直到余数为0，此时较小的那个数就是答案。

为什么能这样？可以这样理解：你有两块木板，一块长12厘米，一块长8厘米。你想切出长度相同、而且是整数倍的小段，且小段要尽可能长。你可以把长木板不断切掉短木板的长度：12切掉一个8，剩下4；然后8切掉两个4，剩下0。最后剩下的那一段（4厘米）就是最大公约数。这就像两个人分东西，每次用大份数减去小份数，直到一模一样大为止。

手工演示：求18和24的最大公约数

24 ÷ 18 = 1 余 6（因为24 = 1×18 + 6）
18 ÷ 6 = 3 余 0（余数为0，停止）
最后的除数6就是最大公约数。

用Python实现辗转相除法

我们可以用while循环来模拟这个过程。代码非常简洁：

def gcd(a, b):
    while b != 0:          # 当余数不为0时继续
        a, b = b, a % b    # 用b替换a，用余数替换b
    return a               # 当b=0时，a就是最大公约数

逐步拆解：假设调用 gcd(18, 24)，变量变化如下：

第一次循环：a=18, b=24 → 计算 a % b = 18 % 24 = 18（因为18小于24，余数就是18本身），然后 a变成24, b变成18
第二次循环：a=24, b=18 → 24 % 18 = 6，然后 a变成18, b变成6
第三次循环：a=18, b=6 → 18 % 6 = 0，然后 a变成6, b变成0
循环结束，返回 a = 6，即为最大公约数

你可能会问：为什么要用 a, b = b, a % b 这种写法？这是Python特有的同时赋值，相当于：

temp = a
a = b
b = temp % b

但更简洁。新手容易在这里犯迷糊，下面会说到。

用Python自带的math.gcd更省事

Python标准库 math 已经提供了现成的最大公约数函数，可以直接用，不用自己写：

import math
print(math.gcd(12, 8))   # 输出 4
print(math.gcd(18, 24))  # 输出 6
print(math.gcd(100, 35)) # 输出 5

这个函数同样基于辗转相除法，但已经帮你处理好边界情况（比如0和负数）。建议在正式项目中使用 math.gcd，自己写函数是为了理解原理。

完整可运行的示例

下面是一个完整的程序，包含了自定义函数、math.gcd对比，以及生活中的应用演示（分糖果问题）：

# 自定义求最大公约数函数（辗转相除法）
def gcd(a, b):
    """
    返回a和b的最大公约数
    """
    while b != 0:          # 当余数不为0时继续
        a, b = b, a % b    # 用b替换a，用余数替换b
    return a               # 当b=0时，a就是最大公约数

# 使用Python自带的math.gcd
import math

# 测试几组数据
num1 = 12  # 糖果数
num2 = 8   # 巧克力数
print(f"{num1}和{num2}的最大公约数是：{gcd(num1, num2)}")  # 输出 4
print(f"验证，math.gcd结果：{math.gcd(num1, num2)}")       # 输出 4

num3 = 18  # 本子数
num4 = 24  # 笔数
g = gcd(num3, num4)
print(f"{num3}和{num4}的最大公约数是：{g}")  # 输出 6
print(f"最多可以分给{g}个同学，每人得到{num3//g}个本子和{num4//g}支笔")

# 再测试几个数
print(gcd(35, 100))   # 输出 5
print(gcd(17, 23))    # 输出 1（互质数）
print(gcd(0, 8))      # 输出 8（特殊：0和任何数的gcd是那个非零数）

运行结果：

12和8的最大公约数是：4
验证，math.gcd结果：4
18和24的最大公约数是：6
最多可以分给6个同学，每人得到3个本子和4支笔
5
1
8

新手容易犯的错误

忘记while循环的条件：有些人会写成 while a != 0 或 while a % b != 0，导致死循环或错误结果。记住判断的是余数b是否为0。
变量交换顺序搞错：正确的写法是 a, b = b, a % b。如果写成 a, b = a % b, b，就会把余数赋给a，b保持不变，循环无法进行。
对取余运算（%）不理解：a % b 得到的是a除以b的余数。比如 12 % 8 = 4，18 % 24 = 18（因为18小于24，商为0，余数就是18）。如果b为0，取余会报错，所以while条件保证了b不为0。
没考虑负数或0：数学上，最大公约数通常定义为非负整数。Python的 math.gcd 会自动处理负数（返回正数），但自定义函数里如果不加处理，输入负数可能导致奇怪结果。可以加一句 a, b = abs(a), abs(b) 来取绝对值。
误以为两个数必须谁大谁小：辗转相除法不需要事先比较大小，因为第一次循环中，如果a小于b，a % b 会直接得到a，然后a和b交换，自动把大的数放在前面。

深度拓展：最大公约数还能做什么？

最大公约数不只是用来分零食，它在数学和编程中非常实用：

简化分数：比如 36/48 的分子分母同时除以它们的最大公约数12，得到 3/4。
求最小公倍数：两个数的最小公倍数（LCM）可以用公式计算：lcm(a, b) = a * b // gcd(a, b)。比如12和8的最小公倍数是 12*8//4 = 24。
判断互质：如果两个数的最大公约数是1，则它们互质。比如15和28，gcd=1，它们没有共同的因数（除了1）。
用在循环节、加密算法（如RSA） 等高级领域。

相关知识点推荐：

最小公倍数（LCM）
更相减损术（另一种求最大公约数的方法，适合大数）
扩展欧几里得算法（用于求解不定方程）
Python的 fractions 模块（分数化简）

学完最大公约数，你就能轻松解决生活中很多“公平分配”的问题啦！下次和同学分零食，你可以骄傲地说：“让我用Python算算最多能分几份！”

Python最大公约数（GCD）