c++如何求两个数的最大公约数_c++求GCD算法实现方法-C++-PHP中文网

c++如何求两个数的最大公约数_c++求GCD算法实现方法

尼克

发布： 2025-10-22 13:26:01

原创

359人浏览过

最大公约数常用欧几里得算法求解，递归和迭代实现均基于GCD(a, b) = GCD(b, a % b)，直至b为0；推荐使用迭代法避免栈溢出，处理负数时取绝对值，多个数的GCD可两两计算。

c++如何求两个数的最大公约数_c++求gcd算法实现方法

在C++中求两个数的最大公约数（GCD，Greatest Common Divisor）有多种方法，最常用且高效的是欧几里得算法（Euclidean Algorithm）。下面介绍几种常见的实现方式。

1. 欧几里得算法（递归实现）

欧几里得算法基于这样一个原理：GCD(a, b) = GCD(b, a % b)，直到其中一个数为0，另一个数就是最大公约数。

#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 << ") = " << gcd(x, y) << endl;
    return 0;
}

登录后复制

输出结果：GCD(48, 18) = 6

2. 欧几里得算法（迭代实现）

避免递归调用，使用循环实现，节省栈空间。

立即学习“C++免费学习笔记（深入）”；

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

登录后复制

逻辑清晰，效率高，适合处理大数或嵌入式环境。

Shakker

多功能AI图像生成和编辑平台

103

查看详情

3. 使用C++标准库 __gcd()

C++17之前，GCC编译器提供了非标准函数 __gcd()，可直接使用（需包含 <algorithm>）。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int x = 48, y = 18;
    cout << "GCD = " << __gcd(x, y) << endl;
    return 0;
}

登录后复制

注意：__gcd() 不是C++标准的一部分，跨平台项目中建议自己实现。

4. 处理负数的情况

最大公约数定义为正整数，若输入可能为负数，应取绝对值。

int gcd(int a, int b) {
    a = abs(a);
    b = abs(b);
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

登录后复制

基本上就这些。推荐使用迭代版欧几里得算法，稳定、高效、可移植性强。遇到求多个数的GCD时，可以两两调用gcd函数，如 gcd(gcd(a,b),c)。

以上就是c++++如何求两个数的最大公约数_c++求GCD算法实现方法的详细内容，更多请关注php中文网其它相关文章！