辗转相减 vs 辗转相除

两种经典方法求最大公约数 (GCD) 的流程对比

欧几里德算法（Euclidean Algorithm）是计算两个非负整数最大公约数（Greatest Common Divisor, GCD）的经典且高效的方法。它主要有两种形式：基于重复减法的“辗转相减法”和基于取余运算的“辗转相除法”。这两种方法都利用了 `gcd(a, b) = gcd(b, a mod b)`（相除法）或 `gcd(a, b) = gcd(a-b, b)`（a>b, 相减法）的核心原理。通过下面的交互式演示，您可以直观地观察并比较这两种算法的执行步骤和效率差异。

输入 a：

输入 b：

请输入两个不同的正整数

辗转相减法 (Subtraction)

辗转相除法 (Division/Modulo)

性能对比

计算步骤数比较

辗转相减法：0 步辗转相除法：0 步

模拟执行时间比较 (ms)

辗转相减法：0 ms 辗转相除法：0 ms

计算结果 GCD(84, 36) = 12

通过本次对比 (a=84, b=36)，我们可以看出：辗转相除法通常比辗转相减法需要更少的步骤（此例中相除法 3 步 vs 相减法 7 步），特别是当两个数差距较大时，效率优势更明显。相除法利用取余运算一步相当于完成了多次相减，因此计算速度更快。然而，相减法的逻辑更为简单直观，更容易理解欧几里德算法的基本思想。

欧几里德算法 C++ 实现示例

辗转相减法

辗转相除法

// C++ 实现辗转相减法求最大公约数
#include 
#include  // C++17 中有 std::gcd
#include  // 用于异常处理

/**
 * @brief 使用辗转相减法计算两个正整数的最大公约数(GCD)
 *
 * @param a 第一个正整数
 * @param b 第二个正整数
 * @return int 返回 a 和 b 的最大公约数
 * @throws std::invalid_argument 如果输入非正整数
 */
long long gcdBySubtraction(long long a, long long b) {
    // 输入校验：确保 a 和 b 都是正整数
    if (a <= 0 || b <= 0) {
        throw std::invalid_argument("输入必须为正整数！");
    }

    int steps = 0; // 用于跟踪步骤数 (可选)

    // 循环直到两个数相等
    while (a != b) {
        steps++;
        if (a > b) {
            a = a - b; // 如果 a 较大, 用 a 减去 b
        } else {
            b = b - a; // 如果 b 较大 (或相等情况理论上已退出), 用 b 减去 a
        }
        // 可以取消下面的注释来观察每一步的状态
        // std::cout << "步骤 " << steps << ": a=" << a << ", b=" << b << std::endl;
    }

    // std::cout << "辗转相减法总共执行了 " << steps << " 步" << std::endl;

    // 当 a == b 时，这个值就是最大公约数
    return a;
}

// 示例用法
// int main() {
//     try {
//         long long num1 = 84, num2 = 36;
//         long long result = gcdBySubtraction(num1, num2);
//         std::cout << "GCD(" << num1 << ", " << num2 << ") = " << result << std::endl; // 输出 GCD(84, 36) = 12
//     } catch (const std::invalid_argument& e) {
//         std::cerr << "错误: " << e.what() << std::endl;
//     }
//     return 0;
// }

// C++ 实现辗转相除法求最大公约数
#include 
#include  // C++17 标准库提供了 std::gcd
#include 

/**
 * @brief 使用辗转相除法 (欧几里德算法标准形式) 计算两个正整数的最大公约数(GCD)
 *
 * @param a 第一个正整数
 * @param b 第二个正整数
 * @return int 返回 a 和 b 的最大公约数
 * @throws std::invalid_argument 如果输入非正整数 (严格来说，算法可处理b=0，但通常要求输入正数)
 */
long long gcdByDivision(long long a, long long b) {
    // 输入校验 (可选，但推荐)
    if (a <= 0 || b <= 0) {
       // 严格来说，gcd(a, 0) = |a|，但通常我们处理正整数对
        throw std::invalid_argument("输入必须为正整数！");
    }

    int steps = 0; // 用于跟踪步骤数 (可选)

    // 循环直到 b (除数) 变为 0
    while (b != 0) {
        steps++;
        long long remainder = a % b; // 计算 a 除以 b 的余数
        a = b;         // 将 b 的值赋给 a
        b = remainder; // 将余数赋给 b

        // 可以取消下面的注释来观察每一步的状态
        // std::cout << "步骤 " << steps << ": a=" << a << ", b=" << b << ", 余数=" << remainder << std::endl;
    }

    // std::cout << "辗转相除法总共执行了 " << steps << " 步" << std::endl;

    // 当 b 为 0 时，a 的值就是最大公约数
    return a;
}

// 示例用法
// int main() {
//     try {
//         long long num1 = 84, num2 = 36;
//         long long result = gcdByDivision(num1, num2);
//         std::cout << "GCD(" << num1 << ", " << num2 << ") = " << result << std::endl; // 输出 GCD(84, 36) = 12
//
//         // 使用 C++17 标准库函数 (如果可用)
//         // #include 
//         // std::cout << "std::gcd(" << num1 << ", " << num2 << ") = " << std::gcd(num1, num2) << std::endl;
//     } catch (const std::invalid_argument& e) {
//         std::cerr << "错误: " << e.what() << std::endl;
//     }
//     return 0;
// }