Python最大公约数算法详解（从零开始掌握欧几里得算法）

方法一：暴力枚举法（适合理解，但效率低）

最直观的方法是从较小的数开始，逐个向下检查是否能同时整除两个数：

def gcd_brute_force(a, b):    # 确保 a 和 b 是正整数    a, b = abs(a), abs(b)    smaller = min(a, b)        for i in range(smaller, 0, -1):        if a % i == 0 and b % i == 0:            return i# 测试print(gcd_brute_force(12, 18))  # 输出: 6

这种方法虽然容易理解，但当数字很大时，效率非常低。因此，我们更推荐使用下面的欧几里得算法。

方法二：欧几里得算法（高效推荐）

欧几里得算法基于一个数学原理：
gcd(a, b) = gcd(b, a mod b)，直到其中一个数变为 0，另一个数就是最大公约数。

例如：计算 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 → gcd(12, 6) = gcd(6, 0) = 6

递归实现

def gcd_recursive(a, b):    if b == 0:        return abs(a)    return gcd_recursive(b, a % b)# 测试print(gcd_recursive(48, 18))  # 输出: 6

迭代实现（更节省内存）

def gcd_iterative(a, b):    a, b = abs(a), abs(b)    while b != 0:        a, b = b, a % b    return a# 测试print(gcd_iterative(48, 18))  # 输出: 6

方法三：使用 Python 内置函数

从 Python 3.5 开始，标准库 math 模块提供了 gcd() 函数，可以直接使用：

import mathprint(math.gcd(48, 18))  # 输出: 6

虽然内置函数方便，但理解其背后的Python GCD教程原理对提升编程能力至关重要。

总结

通过本教程，你已经掌握了三种求最大公约数的方法：暴力法、欧几里得算法（递归与迭代），以及使用 Python 内置函数。对于编程入门者来说，重点应放在理解欧几里得算法的逻辑上，这不仅能解决 GCD 问题，还能帮助你建立算法思维。

记住，Python最大公约数问题虽小，却是通往更高阶算法（如扩展欧几里得、模逆元等）的重要基石。动手写一写代码，加深理解吧！