异常教程
C++ 实例 – 求两数的最大公约数（保姆级教程）
💡一则或许对你有用的小广告
欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论
- 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于
Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;- 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;
截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观
在编程学习的旅程中，数学问题常常是锻炼逻辑思维的重要工具。今天我们将聚焦一个经典问题——C++ 实例 – 求两数的最大公约数，并深入探讨其背后的算法原理与实现方法。无论你是编程初学者还是希望巩固基础的中级开发者，本文都将通过形象的比喻、代码示例和逐步推导，带你系统掌握这一知识点。
什么是最大公约数（GCD）？
最大公约数（Greatest Common Divisor, GCD），指的是两个或多个整数共有约数中最大的一个。例如，12和18的最大公约数是6，因为6是能同时整除这两个数的最大正整数。
- 生活中的类比：想象你有两块蛋糕，一块切成12等份，另一块切成18等份。如果要将它们分成同样大小的“最大块”，每块的大小就是6份。这个“最大块”的概念，就是GCD的核心思想。
在C++中，求解GCD的常见方法包括欧几里得算法、穷举法、更相减损术等。接下来，我们将逐一分析这些方法的原理与实现细节。
方法一：欧几里得算法（经典高效方案）
算法原理
欧几里得算法是求GCD最经典的算法，其核心思想是：
两个数的最大公约数等于较小数与两数余数的最大公约数。
用公式表示为：gcd(a, b) = gcd(b, a mod b)，直到余数为0时，此时的非零数即为GCD。
形象比喻：
想象剥洋葱的过程。每次将较大的数“剥去”较小数的整数倍，剩下的余数继续与较小数重复此操作，直到余数为0，此时剩下的数就是“洋葱的最内层”——最大公约数。
代码实现
递归版本
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
代码解析：
- 当
b为0时，返回a，此时a即为GCD。 - 否则递归调用
gcd(b, a % b)，将问题规模缩小，直到余数为0。
非递归版本
int gcd_iterative(int a, int b) {
while (b != 0) {
int remainder = a % b;
a = b;
b = remainder;
}
return a;
}
对比分析：
- 递归版本：代码简洁，但可能因深度过大导致栈溢出（例如输入极大数）。
- 非递归版本：避免栈溢出风险，适合处理大数，但需手动维护变量状态。
案例演示
假设输入 a = 56, b = 98：
- 第一次循环：
remainder = 56 % 98 = 56（因为56 < 98，余数为自身）
→a = 98,b = 56 - 第二次循环：
remainder = 98 % 56 = 42
→a = 56,b = 42 - 第三次循环：
remainder = 56 % 42 = 14
→a = 42,b = 14 - 第四次循环：
remainder = 42 % 14 = 0
→a = 14,b = 0
最终返回14，即GCD为14。
方法二：穷举法（直观但低效）
算法原理
穷举法通过遍历所有可能的公约数，找到最大的那个。具体步骤如下：
- 从较小的数开始，向下遍历到1。
- 检查该数是否同时能整除两个输入数。
- 第一个符合条件的数即为GCD。
形象比喻：
就像在一堆钥匙中逐个尝试开锁，虽然简单直观，但钥匙数量越多（即输入数越大），尝试的次数就越多。
代码实现
int gcd_brute_force(int a, int b) {
int smaller = (a < b) ? a : b;
for (int i = smaller; i >= 1; i--) {
if (a % i == 0 && b % i == 0) {
return i;
}
}
return 1; // 最小公约数为1
}
效率分析
- 时间复杂度：最坏情况下为
O(min(a, b))，当输入极大时（例如a = 1e9,b = 1e9 + 1），效率极低。 - 适用场景：仅限于小规模输入或教学演示。
方法三：更相减损术（中国古代算法）
算法原理
更相减损术源自《九章算术》，其核心思想是：
两个数的差值与较小数的最大公约数，等同于原两数的GCD。
公式表示为：gcd(a, b) = gcd(b, a - b)（假设a > b）。
形象比喻：
想象两个长度不同的绳子，不断剪下较短绳子的长度，直到两绳等长，此时的长度即为GCD。
代码实现
int gcd_subtraction(int a, int b) {
while (a != b) {
if (a > b) {
a -= b;
} else {
b -= a;
}
}
return a;
}
案例演示
输入 a = 9, b = 6：
- 第一次循环：
a = 9 - 6 = 3→a = 3,b = 6 - 第二次循环：
b = 6 - 3 = 3→a = 3,b = 3
终止循环，返回3。
效率分析
- 时间复杂度：最坏情况下为
O(max(a, b))，例如当两数为连续自然数时（如a = n, b = n-1），需要n-1次减法。 - 优化方向：可通过结合欧几里得算法（如每次减半或取模）提升效率。
算法对比与选择建议
以下表格总结了三种方法的关键指标：
| 方法名称 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 欧几里得算法 | O(log(min(a,b))) | O(1) | 大规模输入，高效稳定 |
| 穷举法 | O(min(a,b)) | O(1) | 小规模输入，教学演示 |
| 更相减损术 | O(max(a,b)) | O(1) | 小规模输入，文化历史兴趣 |
选择建议
- 优先使用欧几里得算法：其时间复杂度对数级，适合绝大多数场景。
- 穷举法或更相减损术：仅用于输入较小或需要直观展示算法流程的情况。
- 结合代码封装：将算法封装为函数，便于复用。例如：
#include <iostream> using namespace std; int gcd(int a, int b) { while (b != 0) { int remainder = a % b; a = b; b = remainder; } return a; } int main() { int num1 = 56, num2 = 98; cout << "GCD of " << num1 << " and " << num2 << " is: " << gcd(num1, num2) << endl; return 0; }
扩展：C++中的标准库支持
C++17引入了<numeric>头文件中的std::gcd函数，可直接调用：
#include <iostream>
#include <numeric>
int main() {
int a = 56, b = 98;
cout << "GCD using std::gcd: " << std::gcd(a, b) << endl;
return 0;
}
注意：此函数要求参数为非负整数，且返回值类型为common_type_t，需确保输入类型兼容。
结论
本文通过欧几里得算法、穷举法、更相减损术三种方法，系统讲解了C++ 实例 – 求两数的最大公约数的实现与优化。无论是理解数学逻辑，还是提升代码效率，欧几里得算法都是最优解。同时，我们通过代码示例与案例分析，帮助读者逐步掌握从理论到实践的完整路径。
希望这篇文章能为你在数学与编程的结合中打开一扇窗，未来在处理类似问题时，能游刃有余地选择最适合的工具与策略！