异常教程
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+ 小伙伴加入学习 ，欢迎点击围观
在编程和数学领域中，最小公倍数（LCM, Least Common Multiple） 是一个基础且重要的概念。无论是解决数学问题还是开发实际应用，掌握如何高效计算两数的最小公倍数都是一项关键技能。本文将以 C++ 实例 – 求两数最小公倍数 为主题，从数学基础、算法实现到代码优化，逐步引导读者理解这一问题，并通过实例代码和案例分析，帮助读者巩固知识。
数学基础：什么是最小公倍数？
最小公倍数是指两个或多个整数共有的倍数中最小的一个正整数。例如，数字 4 和 6 的倍数分别为：
- 4 的倍数：4, 8, 12, 16, 20, 24,…
- 6 的倍数：6, 12, 18, 24, 30,…
它们的最小公倍数是 12。
与最大公约数（GCD）的关系
最小公倍数的计算通常与最大公约数（GCD）相关联。数学公式表明：
LCM(a, b) = (a × b) / GCD(a, b)
这个公式背后的逻辑可以用“齿轮咬合”来比喻：假设两个齿轮的齿数分别为 a 和 b，当它们同时转动时，第一次完全重合的步数即为 LCM(a, b)。而 GCD 则代表它们的“共同齿数”，即两个齿轮共享的最小旋转周期。
算法思路：如何高效求解 LCM？
第一步：计算 GCD
计算 LCM 的核心在于先求出 GCD。最经典的算法是 欧几里得算法，其步骤如下：
- 用较大的数除以较小的数，取余数。
- 将较小的数作为新的被除数，余数作为除数，重复步骤 1。
- 直到余数为 0，此时的除数即为 GCD。
例如，计算 GCD(18, 24)：
- 24 ÷ 18 = 1 余 6
- 18 ÷ 6 = 3 余 0 → GCD = 6
第二步：利用 GCD 计算 LCM
根据公式 LCM(a, b) = (a × b) / GCD(a, b)，只需将 GCD 的结果代入即可。但需要注意两点：
- 避免因 a × b 过大导致的溢出问题（尤其当 a 和 b 是大整数时）。
- 处理 a 或 b 为 0 的情况（此时 LCM 也应为 0）。
代码实现：从基础到优化
以下代码逐步演示如何用 C++ 实现 LCM 的计算，并通过优化减少潜在问题。
示例 1：基础版代码
#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 lcm(int a, int b) {
return (a / gcd(a, b)) * b; // 先除后乘，避免溢出
}
int main() {
int num1 = 12, num2 = 18;
cout << "LCM of " << num1 << " and " << num2 << " is: " << lcm(num1, num2);
return 0;
}
代码解析
gcd函数通过循环实现欧几里得算法。lcm函数采用 先除后乘 的方式，避免 a × b 的直接计算导致溢出。- 主函数中测试了 12 和 18，输出结果为 36。
示例 2：函数封装与错误处理
为了提高代码的健壮性，可以添加对输入为 0 的判断，并封装成独立函数：
#include <iostream>
using namespace std;
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;
}
int lcm(int a, int b) {
if (a == 0 || b == 0) return 0; // 0 的 LCM 定义为 0
return (a / gcd(a, b)) * b;
}
// 测试函数
void test_lcm() {
cout << "Test Case 1: " << lcm(0, 5) << " (Expected: 0)" << endl;
cout << "Test Case 2: " << lcm(-4, 6) << " (Expected: 12)" << endl;
cout << "Test Case 3: " << lcm(15, 25) << " (Expected: 75)" << endl;
}
int main() {
test_lcm();
return 0;
}
改进点
- 处理负数：通过
abs()将输入转为正数，确保 GCD 计算的正确性。 - 零值判断：直接返回 0，符合数学定义。
- 测试函数：通过多个测试用例验证代码的鲁棒性。
进阶优化：避免溢出与提升效率
问题 1：大数溢出
当 a 和 b 非常大时，a / gcd(a, b) 可能超出整型范围。例如：
// 假设 a = 2^30, b = 2^30 → GCD = 2^30
// 则 (a / GCD) * b = 1 * 2^30 = 2^30 → 仍可能溢出
解决方案
改用 long long 类型存储中间结果，或使用更安全的算法（如 __int128，但需编译器支持）：
#include <cstdint>
long long lcm_large(int a, int b) {
if (a == 0 || b == 0) return 0;
return static_cast<long long>(a) / gcd(a, b) * b;
}
问题 2：负数的处理
虽然 LCM 通常定义为正数，但代码需兼容负数输入，例如：
// 测试案例
cout << lcm(-12, 18) << endl; // 输出应为 36
常见错误与调试技巧
错误 1：未处理零值
// 错误代码：未判断 a 或 b 为 0 的情况
int lcm(int a, int b) {
return (a * b) / gcd(a, b); // 当 a=0 时，结果错误
}
修正代码
int lcm(int a, int b) {
if (a == 0 || b == 0) return 0;
return (a / gcd(a, b)) * b;
}
错误 2：溢出未被发现
// 当 a=1e9, b=1e9 → a*b = 1e18，超出 int 范围（2^31 ≈ 2e9）
解决方案
改用 long long 类型：
long long lcm(int a, int b) {
return static_cast<long long>(a) * b / gcd(a, b);
}
扩展应用：LCM 的实际场景
案例 1：安排周期性事件
假设需要安排两个周期性任务：
- 任务 A 每 6 天执行一次
- 任务 B 每 8 天执行一次
问题：它们第一次同时执行的时间是第几天？
解答：LCM(6, 8) = 24 → 第 24 天。
案例 2：分数运算
在分数加减法中，通分需要找到分母的 LCM。例如：
1/4 + 1/6 = (3/12 + 2/12) = 5/12 → LCM(4, 6) = 12
结论
通过本文的学习，读者应能掌握以下核心内容：
- 数学基础：理解 LCM 与 GCD 的关系，以及其实用性。
- 算法实现：从欧几里得算法到代码封装的完整流程。
- 优化与调试：处理溢出、负数和零值等边界情况。
C++ 实例 – 求两数最小公倍数 的实现不仅是一道编程题，更是数学思维与代码实践的结合。掌握这一技能后，读者可以将其应用于更复杂的场景，如算法竞赛、工程计算等。建议读者通过实际编写代码、测试不同输入值，进一步巩固对这一知识点的理解。
希望本文能为编程初学者和中级开发者提供清晰的指导，并激发对数学与编程结合的兴趣！