C++最大公约数算法详解（从零开始掌握欧几里得算法与辗转相除法）

什么是最大公约数？

最大公约数（Greatest Common Divisor，简称 GCD）是指两个或多个整数共有约数中最大的一个。例如：

• 12 的约数有：1, 2, 3, 4, 6, 12
• 8 的约数有：1, 2, 4, 8
• 它们的公共约数是：1, 2, 4
• 所以最大公约数是：4

C++中常用的求最大公约数方法

在 C++ 中，最经典、高效的算法是欧几里得算法（又称辗转相除法）。这个算法基于以下数学原理：

gcd(a, b) = gcd(b, a mod b)，直到 b 为 0，此时 a 就是最大公约数。

方法一：递归实现欧几里得算法

#include <iostream>using namespace std;// 递归方式实现最大公约数int gcd(int a, int b) {    if (b == 0)        return a;    return gcd(b, a % b);}int main() {    int x = 48, y = 18;    cout << "最大公约数是: " << gcd(x, y) << endl;    return 0;}

方法二：循环实现辗转相除法

如果你不习惯递归，也可以用 while 循环来实现：

#include <iostream>using namespace std;// 循环方式实现最大公约数int gcd(int a, int b) {    while (b != 0) {        int temp = b;        b = a % b;        a = temp;    }    return a;}int main() {    int x = 48, y = 18;    cout << "最大公约数是: " << gcd(x, y) << endl;    return 0;}

为什么欧几里得算法高效？

欧几里得算法C++实现之所以高效，是因为它每次都将问题规模显著缩小。数学上可以证明，该算法的时间复杂度为 O(log(min(a, b)))，远优于暴力枚举法。

注意事项

• 确保输入的是非负整数（可先取绝对值处理）
• 当其中一个数为 0 时，最大公约数就是另一个数
• C++17 及以上标准中，可以直接使用标准库函数 std::gcd（需包含 <numeric> 头文件）

使用标准库（C++17）

#include <iostream>#include <numeric> // 包含 gcd 函数using namespace std;int main() {    int x = 48, y = 18;    cout << "最大公约数是: " << gcd(x, y) << endl;    return 0;}

总结

通过本教程，你已经掌握了 C++最大公约数算法的核心思想和多种实现方式。无论是使用辗转相除法C++手动实现，还是借助现代 C++ 标准库，都能轻松解决最大公约数问题。这是每个学习 C++编程入门教程 的开发者必须掌握的基础技能之一。

动手试试吧！修改代码中的数字，观察输出结果，加深理解。编程能力就是在一次次实践中提升的！