嘿，很高兴你问这个问题！计算两个数的最大公约数最经典、最常用的就是欧几里得算法（Euclidean Algorithm），我先给你展示一段典型的实现代码，再一步步拆解它的工作原理：

1. 常见代码实现 #

迭代版（更稳定，适合大数计算） #

def gcd(a, b):
    # 先处理负数，因为GCD的结果与正负无关
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a

递归版（代码更简洁） #

def gcd_recursive(a, b):
    a, b = abs(a), abs(b)
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

2. 算法核心原理 #

欧几里得算法的核心基于一个关键数学定理：两个正整数a和b的最大公约数，等于b和a除以b的余数的最大公约数，用公式表示就是：
gcd(a, b) = gcd(b, a % b)

咱们拿具体例子gcd(48, 18)来走一遍流程，你就能秒懂：

• 第一步：48 ÷ 18 = 2 余 12 → gcd(48, 18) = gcd(18, 12)
• 第二步：18 ÷ 12 = 1 余 6 → gcd(18, 12) = gcd(12, 6)
• 第三步：12 ÷ 6 = 2 余 0 → 当余数为0时，当前的第一个数（也就是6）就是原来两个数的最大公约数

为什么这个定理成立？简单来说：
如果d是a和b的公约数，那d一定能整除a和b，自然也能整除a - k*b（k是整数）。而a % b本质就是a减去若干个b后剩下的小于b的数（或0），所以d也能整除a % b，也就是d是b和a%b的公约数。反过来，如果d是b和a%b的公约数，那它也能整除a，所以两边的公约数集合完全相同，最大的那个自然相等。

3. 代码逐行解释（迭代版） #

• 先通过abs()处理负数，因为最大公约数的结果和输入数的正负无关
• 进入while循环，循环条件是b != 0——只要余数不为0，就继续迭代
• 每次循环里，我们把b赋值给新的a，把a % b（余数）赋值给新的b，相当于把问题拆解成更小的子问题
• 当b变成0时，循环终止，此时的a就是最初两个数的最大公约数

4. 额外补充：更高效的Stein算法 #

如果是处理非常大的整数（比如几百位的大数），欧几里得算法的取模操作会比较耗时，这时候可以用Stein算法（也叫二进制GCD算法），它通过移位和减法来替代取模，效率更高。不过对于绝大多数日常场景，欧几里得算法已经足够好用啦。

内容的提问来源于stack exchange，提问作者Robert