最大公约数常用欧几里得算法求解，递归和迭代实现均基于GCD(a, b) = GCD(b, a % b)，直至b为0；推荐使用迭代法避免栈溢出，处理负数时取绝对值，多个数的GCD可两两计算。
在C++中求两个数的最大公约数（GCD，Greatest Common Divisor）有多种方法，最常用且高效的是欧几里得算法（Euclidean Algorithm）。下面介绍几种常见的实现方式。
1. 欧几里得算法（递归实现）
欧几里得算法基于这样一个原理：GCD(a, b) = GCD(b, a % b)，直到其中一个数为0，另一个数就是最大公约数。
#include 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;}
逻辑清晰，效率高，适合处理大数或嵌入式环境。
3. 使用C++标准库 __gcd()
C++17之前，GCC编译器提供了非标准函数 __gcd()，可直接使用（需包含 ）。
#include #include 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算法实现方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1480355.html
微信扫一扫 
支付宝扫一扫 
