辗转相除法求最大公约数及与更相减损术的对比

计算两个数的最大公约数（Greatest Common Divisor， GCD）是数学和计算机科学中的基础问题。它指两个或多个整数共有约数中最大的一个。掌握高效的求解方法在处理分数化简、密码学算法等领域至关重要。

本文将直接讲解两种经典算法，并提供可立即执行的步骤和代码。

1. 理解核心算法：辗转相除法（欧几里得算法）

辗转相除法基于一个核心原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。 用公式表示，若 $a$ 和 $b$ 是两个正整数，且 $a > b$，则 $gcd(a， b) = gcd(b， a \mod b)$。

这个原理可以递归或循环应用，直到余数为 0，此时的除数就是最大公约数。

具体操作步骤（以计算 gcd(252， 105) 为例）：

1. 确认较大数 a 和较小数 b。此处 a = 252， b = 105。
2. 计算 a 除以 b 的余数 r。计算 252 ÷ 105， 商为 2，余数为 252 - 105 * 2 = 42。
3. 判断余数 r 是否为 0。如果 r 为 0，则当前的 b 就是最大公约数，停止。
4. 将 b 的值赋予 a，将 r 的值赋予 b，然后回到第 2 步继续。现在 a = 105， b = 42。
5. 重复计算 105 ÷ 42， 商 2， 余数 21。余数不为 0，所以 a = 42， b = 21。
6. 重复计算 42 ÷ 21， 商 2， 余数 0。余数为 0，停止。此时的除数 b（值为 21）就是 252 和 105 的最大公约数。

252 和 105 的最大公约数是 21。

2. 理解对比算法：更相减损术

更相减损术出自中国古代数学著作《九章算术》，其核心是“以较数减较数，以多减少”。基本原理是：两个正整数的差与较小数的最大公约数，等于这两个数本身的最动词公约数。 即 $gcd(a， b) = gcd(b， a-b)$（其中 $a > b$）。

具体操作步骤（同样以计算 gcd(252， 105) 为例）：

1. 确认两个数 a 和 b。此处 a = 252， b = 105。
2. 判断 a 和 b 是否相等。如果相等，则这个数就是最大公约数，停止。
3. 计算较大数减去较小数的差 d。计算 252 - 105 = 147。
4. 将差 d 与原来较小的数 b 组成新的一对数。现在新的一对数是 147 和 105。
5. 回到第 2 步，对 147 和 105 继续操作。
6. 重复：147 - 105 = 42， 新一对数变为 105 和 42。
7. 重复：105 - 42 = 63， 新一对数变为 63 和 42。
8. 重复：63 - 42 = 21， 新一对数变为 42 和 21。
9. 重复：42 - 21 = 21， 新一对数变为 21 和 21。
10. 判断到两个数相等，均为 21，停止。21 就是最大公约数。

3. 方法对比与分析

关键结论：对于绝大多数实际应用，辗转相除法是效率远高于更相减损术的标准解决方案。更相减损术的价值在于其算法思想的历史意义和在特定理论场景中的演示作用。

4. 实用代码示例

以下是两种算法的 Python 实现，可以直接复制运行。

辗转相除法实现：

def gcd_euclidean(a， b):
    """使用辗转相除法（迭代版本）计算最大公约数"""
    # 确保 a >= b
    while b != 0:
        a， b = b， a % b
    return a

# 测试
print(gcd_euclidean(252， 105))  # 输出: 21

更相减损术实现（含半之优化）：

def gcd_gengxiang(a， b):
    """使用更相减损术（含‘半之’优化）计算最大公约数"""
    # 先处理公共的2因子
    shift = 0
    while ((a | b) & 1) == 0:  # 如果 a 和 b 都是偶数
        a >>= 1
        b >>= 1
        shift += 1

    # 现在 a 或 b 至少有一个是奇数
    while (a & 1) == 0:  # 如果 a 是偶数
        a >>= 1

    while b != 0:
        # 确保 b 是偶数，以便不断减半
        while (b & 1) == 0:
            b >>= 1
        # 现在 a 和 b 都是奇数
        if a < b:
            a， b = b， a
        a = a - b

    return a << shift  # 将之前提取的公因子2乘回去

# 测试
print(gcd_gengxiang(252， 105))  # 输出: 21

使用标准库：
在 Python 中，最简便的方式是使用内置函数 math.gcd。

import math
print(math.gcd(252， 105))  # 输出: 21

对于绝大多数编程任务，直接调用经过高度优化的库函数是最佳实践。理解其背后的算法原理，则有助于在面试、算法设计或特殊环境中做出正确判断。