FANGT

最大公约数

作者：

fangys

定义

最大公约数（Greatest Common Divisor, GCD）是指两个或多个整数共有约数中最大的一个。 例如，12 和 18 的公约数有 1、2、3、6，其中最大的 6 就是它们的最大公约数。 最大公约数在数学、密码学、分数化简等领域有广泛应用。

方案

  • 枚举法（穷举法）：从较小的数开始向下（或向上）逐一检验，找到最大的能同时整除两个数的数。
  • 辗转相除法（欧几里得算法）：反复用较大数除以较小数取余，直到余数为零，此时除数即为最大公约数。
  • 更相减损法：古代《九章算术》中的方法，通过反复相减（或结合提取公因子 2）得到最大公约数。
  • Stein 算法：一种优化的大整数求 GCD 算法，主要针对二进制运算。

具体代码

枚举法（穷举法）

输入两个正整数 (a, b)，设较小数为 (minVal)。从 (minVal) 开始向下递减到 1，检查每个数是否能同时整除 (a) 和 (b)。第一个满足条件的数即为最大公约数。

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    // 取较小数
    int minVal = (a < b) ? a : b;
    int gcd = 1;

    // 从 minVal 向下枚举
    for (int i = minVal; i >= 1; i--) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
            break;  // 找到即退出循环
        }
    }

    cout << gcd << endl;
    return 0;
}

辗转相除法（欧几里得算法）

用较大数除以较小数得到余数，然后用除数代替被除数，余数代替除数，重复此过程直到余数为 0，此时的除数就是最大公约数。 （算法中不需要判断大小，因为取余运算会自动处理）

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    int x = a, y = b;  // 保存原始值，以便输出时使用
    // 辗转相除
    while (y != 0) {
        int r = x % y;
        x = y;
        y = r;
    }
    // 此时 x 即为最大公约数

    cout << x << endl;
    return 0;
}

更相减损法（《九章算术》）

  1. 输入两个正整数 a 和 b。
  2. 若 a=b，则最大公约数为 a（或 b），算法结束。
  3. 若 a≠b，则用较大数减去较小数，用差替换较大数。
  4. 重复步骤 2 和 3，直到两数相等为止，此时相等的数即为最大公约数。
#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    int x = a, y = b;
    // 当两数不相等时，不断用大数减小数
    while (x != y) {
        if (x > y)
            x = x - y;
        else
            y = y - x;
    }
    // 此时 x == y，即为最大公约数

    cout << x << endl;
    return 0;
}

总结

方法优点缺点
枚举法简单直观效率低，适合小整数
辗转相除法效率高，稳定需要取模运算
更相减损法古代算法，适合手工计算基础版效率较低，优化后较好

以上三种方法均能正确计算最大公约数，实际编程中推荐使用辗转相除法，其代码简洁且效率最高。