C++ 最大公约数与最小公倍数

最大公约数（GCD）是指能够同时整除两个整数的最大正整数，最小公倍数（LCM）则是指能够同时被两个整数整除的最小正整数。比如对于 48 和 18 来说，它们的最大公约数是 6，最小公倍数是 144。

在 C++ 中求解这两个值，常见的有 2 种方式：① 使用 “辗转相除法” 手写循环求解；② 直接调用 <numeric> 头文件提供的标准库函数。

手写辗转相除法求解

如果在程序里把两个数的所有约数、所有倍数一个个列出来再找答案，不仅代码繁琐，遇到大数字时运行还会非常慢。更高效的做法是先通过 “辗转相除法” 求出最大公约数，再根据最大公约数直接算出最小公倍数。

1. 求最大公约数

辗转相除法也叫欧几里得算法。比如 48 除以 18 的商是 2、余数是 12（即 48 = 18 × 2 + 12），凡是能同时整除 48 和 18 的数，必然也能整除余数 12。也就是说，两个正整数 a 和 b 的最大公约数，等于除数 b 与余数 a % b 的最大公约数。

在代码中，我们可以借助取余运算符（%）算出两数相除的余数，再让原来的除数变成新的被除数、余数变成新的除数。这样反复除下去，直到余数变成 0 时，最后那个非 0 的除数就是最大公约数。

拿 48 和 18 来说，每次取余的计算过程如下：

48 % 18 = 12
18 % 12 = 6
12 % 6 = 0

第 1 次算出余数 12 后，下一轮我们就接着算 18 和 12。第 2 次算出余数 6 后，下一轮再算 12 和 6。到了第 3 次，余数刚好变成 0，此时的除数 6 就是最大公约数。由于事先不确定一共要除多少次，写代码时非常适合使用 while 循环来控制。

2. 求最小公倍数

在数学上，两个正整数的乘积，刚好等于它们的最大公约数与最小公倍数的乘积。因此，只要我们先求出了最大公约数 gcd，就可以通过下面的算式一步算出最小公倍数：

lcm = a / gcd * b
48 / 6 * 18 = 8 * 18 = 144

已知 48 和 18 的最大公约数是 6，我们先算 48 / 6 得到 8，再乘以 18 就能得出最小公倍数 144。下面我们把求最大公约数和求最小公倍数的逻辑分别封装成函数。

示例 1：手写辗转相除法

#include <iostream>

// 使用辗转相除法求最大公约数
int getGcd(int a, int b) {
    while (b != 0) {
        int rem = a % b;    // 计算 a 除以 b 的余数
        a = b;              // 除数变成新的被除数
        b = rem;            // 余数变成新的除数
    }
    return a;               // b 为 0 时返回 a
}

// 根据最大公约数求最小公倍数
int getLcm(int a, int b) {
    if (a == 0 || b == 0) {
        return 0;           // 含 0 时最小公倍数为 0
    }
    return a / getGcd(a, b) * b;
}

int main() {
    int a = 48;
    int b = 18;

    std::cout << a << " 和 " << b << " 的最大公约数：" << getGcd(a, b) << '\n';
    std::cout << a << " 和 " << b << " 的最小公倍数：" << getLcm(a, b) << '\n';
    return 0;
}

运行结果如下。

48 和 18 的最大公约数：6
48 和 18 的最小公倍数：144

分析：

在这个例子中，我们重点看看 getGcd() 最后一轮退出循环时的变量变化。当 12 % 6 算出余数 rem 为 0 后，程序接着执行 a = b; 和 b = rem;，把除数 6 赋给了 a、余数 0 赋给了 b。随后 b != 0 不再成立，循环结束，因此最终保存最大公约数 6 的变量正好是 a，而不是 b。

再看 getLcm() 函数：由于 0 没有正整数倍，包含 0 时最小公倍数通常记为 0。因此我们在函数开头先通过 if (a == 0 || b == 0) 处理了包含 0 的特殊情况，随后再调用 getGcd(a, b) 计算结果。

可能有些小伙伴会问：“如果调用 getGcd(18, 48)，第 1 个数比第 2 个数小，需要先交换 a 和 b 吗？” 其实不用。当 a = 18、b = 48 时，第 1 轮算出 18 % 48 的余数为 18，执行赋值后 a 就变成了 48、b 变成了 18，大小顺序已经自动调过来了。

使用 std::gcd() 和 std::lcm()（推荐）

手写辗转相除法非常适合用来练习循环和变量更新，但在实际项目开发中，如果我们只需要直接拿到计算结果，没必要每次都自己手写一遍。

从 C++17 标准开始，C++ 在 <numeric> 头文件中直接提供了现成的 std::gcd() 和 std::lcm() 函数，只需一行代码就能算出答案。下面我们来看一个例子。

示例 2：调用标准库函数求解

#include <iostream>
#include <numeric>    // 提供 std::gcd() 和 std::lcm()

int main() {
    int a = 48;
    int b = 18;

    std::cout << "std::gcd(48, 18) = " << std::gcd(a, b) << '\n';
    std::cout << "std::lcm(48, 18) = " << std::lcm(a, b) << '\n';
    return 0;
}

运行结果如下。

std::gcd(48, 18) = 6
std::lcm(48, 18) = 144

分析：

std::gcd(a, b) 和 std::lcm(a, b) 都定义在 <numeric> 头文件中，调用时我们直接传入两个整数即可。此外，这两个函数内部已经处理好了传入 0 或负数的情况，比如调用 std::gcd(-48, 18) 同样会返回非负结果 6。

平时小伙伴们做算法练习要求手写实现过程时，可以使用前面介绍的辗转相除法。而在日常项目开发中，我们直接调用这两个标准库函数会省心很多。