欧几里得算法

#欧几里得算法

• 什么是欧几里得算法
• 操作步骤
• 为什么有效
• 特点

#什么是欧几里得算法

欧几里得算法（又称辗转相除法）用于计算两个数的最大公约数（GCD），被称为世界上最古老的算法，最早记载于公元前 300 年欧几里得的著作中。

#操作步骤

核心操作就是反复做取余（mod）运算：用较大的数除以较小的数，得到余数；然后用除数和余数继续重复，直到余数为 0。

以求 1112 和 695 的最大公约数为例：

1112 mod 695 = 417    ← 用 1112 除以 695，余 417
 695 mod 417 = 278    ← 用 695 除以 417，余 278
 417 mod 278 = 139    ← 用 417 除以 278，余 139
 278 mod 139 = 0      ← 余数为 0！

→ 最大公约数 = 139（最后一次的除数）

Python 实现：

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(1112, 695))  # => 139

#为什么有效

把两个数看作两条线段，最大公约数就是能同时整分这两条线段的最大单位：

1112 = 139 × 8
 695 = 139 × 5
GCD  = 139

余数也一定是 139 的整数倍:
 417 = 139 × 3
 278 = 139 × 2

每次取余后，余数仍然能被最大公约数整除。当余数为 0 时，最后一次的除数就是最大公约数。

#特点

• 只需重复做除法，不需要因式分解
• 即使两个数字很大，也能高效求解
• 与分而治之思想相通（D&C 中土地分方块的例子本质就是欧几里得算法）
• 时间复杂度为 O(log(min(a,b)))

#小结

• 欧几里得算法通过反复取余求最大公约数
• 余数为 0 时，最后一次的除数就是 GCD
• 简单高效，是最古老的算法之一