首页 > 编程语言 >Python实现欧几里得算法求最大公约数

Python实现欧几里得算法求最大公约数

来源：互联网 2026-06-27 07:55:02

python资讯合集

欧几里得算法（辗转相除法）通过反复用较小数除较大数取余，核心公式gcd(a,b)=gcd(b,amodb)，快速计算两个自然数的最大公约数，直至余数为零。Python递归实现代码极简，效率高；图形验证显示结果呈周期性规律。该算法历史悠久，广泛应用于数论与密码学。

最大公约数（GCD）是数学中的基础概念，但小学教育往往只涉及定义，忽略了高效计算方法。欧几里得算法（Euclidean Algorithm）正是解决这一问题的经典方法——它能在两个自然数不同时为零的情况下，快速求出它们的最大公约数。本文将逐步解析该算法，帮助读者深入理解。

从暴力计算说起

直接根据定义硬算，思路很直观：从较小的数开始递减，直到找到能同时整除两个数的数。逻辑正确，但效率低下。

长期稳定更新的攒劲资源： >>>点此立即查看<<<

对应的Python代码如下：

def brute_force_gcd(a, b):
    if a == 0 and b == 0:
        raise ValueError("a and b cannot be both 0")
    if a == 0:
        return b
    if b == 0:
        return a
    candidate = min(a, b)
    while True:
        if a % candidate == 0 and b % candidate == 0:
            return candidate
        candidate -= 1

由于所有自然数都能被1整除，因此最大公约数至少为1。

观察规律：固定一个数，看看有什么发现

接下来，我们采用数学研究中的常用方法：寻找规律。固定其中一个数 b 不变，让 a 变动（反之亦然，结果相同），观察 gcd 的变化模式。

b = 1 时

当 b=1 时，无论 a 取何值，gcd(a,1) = 1，显而易见。

b = 2 时

当 b=2 时，列举几个 a 值：

Python实现欧几里得算法求最大公约数

规律清晰——结果不是1就是2，交替出现。原因如下：
a 为偶数时，2能整除 a 和 2，gcd=2；
a 为奇数时，2无法整除 a，gcd=1。

b = 3 时

同样，观察 b=3 的情况：

Python实现欧几里得算法求最大公约数

周期为3,1,1，重复循环。解释如下：
a ≡ 0 (mod 3) 时，3能同时整除 a 和 3，gcd=3；
a ≡ 1 (mod 3) 时，3无法整除 a，且2不能整除3，gcd=1；
a ≡ 2 (mod 3) 时，同理，gcd=1。

b = 4 时

再看 b=4：

Python实现欧几里得算法求最大公约数

结果为4,1,2,1，周期为4。分析如下：
a ≡ 0 (mod 4) → gcd=4；
a ≡ 1 (mod 4) → 4无法整除 a，3不能整除4，2不能整除 a，因此 gcd=1；
a ≡ 2 (mod 4) → 4无法整除 a，但2能同时整除 a 和 4，gcd=2；
a ≡ 3 (mod 4) → 所有除数均不满足，gcd=1。

推广到一般情况

从以上例子可以尝试提炼通用规律。假设 a ≥ b，以下等式成立：

gcd(a, b) = gcd(a - b, b)

尝试证明。记 gcd(a,b)=g，gcd(a-b,b)=g'。

从左向右推导：
由于 g|a 且 g|b，故 g|(a-b)。g 既是 a-b 的约数，也是 b 的约数，因此是 a-b 和 b 的公约数，从而 g ≤ g'。

从右向左推导：
由于 g'|(a-b) 且 g'|b，故 g'|((a-b)+b)，即 g'|a。g' 既是 a 的约数，也是 b 的约数，因此 g' ≤ g。

结合得 g ≤ g' 且 g' ≤ g，故 g = g'。证毕。

基于这一结论，可以不断相减：

gcd(a,b) = gcd(a-b,b) = gcd(a-2b,b) = ... = gcd(a mod b, b)

这就是欧几里得算法的核心思想。

用Python实现欧几里得算法

以55和34为例进行计算：

gcd(55,34) = gcd(55 mod 34, 34) = gcd(21,34)
= gcd(34 mod 21, 21) = gcd(13,21)
= gcd(21 mod 13, 13) = gcd(8,13)
= gcd(13 mod 8, 8) = gcd(5,8)
= gcd(8 mod 5, 5) = gcd(3,5)
= gcd(5 mod 3, 3) = gcd(2,3)
= gcd(3 mod 2, 2) = gcd(1,2)
= gcd(2 mod 1, 1) = gcd(0,1)
= 1

对应的代码简洁高效：

def gcd(a, b):
    if (a, b) == (0, 0):
        raise ValueError("a and b cannot be both 0")
    if b == 0:
        return a
    return gcd(b, a % b)

为直观展示调用过程，在 trae 的帮助下添加一个 show_stack 方法（无需关注实现细节，仅用于查看调用栈）：

import inspect
def gcd(a, b):
    if (a, b) == (0, 0):
        raise ValueError("a and b cannot be both 0")
    if b == 0:
        show_stack()
        return a
    return gcd(b, a % b)

def show_stack():
    for frame_info in inspect.stack()[:][1:]:
        frame = frame_info.frame
        args = []
        for name in frame.f_code.co_varnames[:frame.f_code.co_argcount]:
            if name in frame.f_locals:
                args.append(f"{name}={frame.f_locals[name]}")
        print(f"{frame_info.function}({', '.join(args)})")

if __name__ == "__main__":
    gcd(55, 34)

保存为 calc_gcd.py，运行 python3 calc_gcd.py，输出如下：

gcd(a=1, b=0)
gcd(a=2, b=1)
gcd(a=3, b=2)
gcd(a=5, b=3)
gcd(a=8, b=5)
gcd(a=13, b=8)
gcd(a=21, b=13)
gcd(a=34, b=21)
gcd(a=55, b=34)
()

可见，调用顺序反转即为完整的计算路径。

验证一下

通过绘图验证算法正确性。以下代码调用欧几里得算法并生成图表：

import matplotlib.pyplot as plt

def gcd(a, b):
    if (a, b) == (0, 0):
        raise ValueError("a and b cannot be both 0")
    if b == 0:
        return a
    return gcd(b, a % b)

def plot_gcd_results(nums, gcd_results, b):
    plt.figure(figsize=(12, 8))
    plt.bar(nums, gcd_results, color='skyblue', edgecolor='black')
    plt.xlabel('a', fontsize=12)
    plt.ylabel('GCD(a, %d)' % b, fontsize=12)
    plt.title('GCD(a, %d) for a from %d to %d' % (b, nums[0], nums[-1]), fontsize=14)
    plt.xticks(nums)
    plt.yticks(range(max(gcd_results) + 1))
    plt.grid(axis='y', linestyle='--')
    plt.tight_layout()
    plt.show()

if __name__ == "__main__":
    b = 4
    nums = range(5 * b + 1)
    gcd_results = [gcd(num, b) for num in nums]
    plot_gcd_results(nums, gcd_results, b)

运行结果如下：

Python实现欧几里得算法求最大公约数