C 练习实例16 – 最大公约数和最小公倍数：从零理解算法核心
在学习 C 语言的过程中，我们总会遇到一些经典问题，它们看似简单，却能深刻锻炼我们的逻辑思维与编程能力。今天我们要讲的是“C 练习实例16 – 最大公约数和最小公倍数”，这个题目不仅出现在各大编程教材中，也是面试中常被考察的基础算法题之一。
你可能已经听说过“最大公约数”（GCD）和“最小公倍数”（LCM）这两个词，但它们到底是什么？为什么我们要计算它们？其实，它们在现实生活中的应用非常广泛：比如，当你想把两个不同长度的木板切割成相同长度的小段，且要求每段尽可能长，这就涉及到最大公约数；而如果你要安排两个周期性事件（如两辆公交车的发车时间）何时首次同时发生，那就要用到最小公倍数。
接下来，我们就一起动手，从基础概念出发，逐步实现这两个经典算法的 C 语言版本。
理解最大公约数与最小公倍数的本质
先来定义清楚两个概念：
- 最大公约数（Greatest Common Divisor, GCD）：两个或多个整数共有的最大正整数因数。例如，12 和 18 的公约数有 1、2、3、6，其中最大的是 6，所以 GCD(12, 18) = 6。
- 最小公倍数（Least Common Multiple, LCM）：两个或多个整数共有的最小正整数倍数。例如，12 和 18 的公倍数有 36、72、108……最小的是 36，所以 LCM(12, 18) = 36。
它们之间还有一个非常重要的数学关系：
a × b = GCD(a, b) × LCM(a, b)
这意味着，只要我们求出 GCD，就可以快速算出 LCM，反之亦然。
这个公式就像一个“双生子”关系，一个知道，另一个就“自动浮现”。在编程实现中，我们可以利用这个性质，先求 GCD，再通过公式推导 LCM，避免重复计算。
方法一：暴力枚举法（适合初学者理解）
最直观的方法，就是从 1 开始，逐个检查每个数是否能同时整除两个输入数。我们从 1 一直试到较小的那个数为止。
#include <stdio.h>
// 求最大公约数：暴力枚举法
int gcd_by_brute_force(int a, int b) {
int min = a < b ? a : b; // 找出两个数中较小的那个
int result = 1; // 默认最大公约数至少是 1
// 从 1 到 min，逐个检查是否能整除 a 和 b
for (int i = 1; i <= min; i++) {
if (a % i == 0 && b % i == 0) {
result = i; // 如果当前 i 是公约数，就更新 result
}
}
return result;
}
// 求最小公倍数：利用公式 LCM = (a * b) / GCD
int lcm_by_formula(int a, int b, int gcd) {
return (a * b) / gcd;
}
int main() {
int num1, num2;
printf("请输入两个正整数：");
scanf("%d %d", &num1, &num2);
int gcd = gcd_by_brute_force(num1, num2);
int lcm = lcm_by_formula(num1, num2, gcd);
printf("最大公约数为：%d\n", gcd);
printf("最小公倍数为：%d\n", lcm);
return 0;
}
代码说明：
min = a < b ? a : b;：三目运算符判断哪个数更小，因为我们最多只能找比它小的公约数。for循环从 1 到min，检查每个数是否能同时整除 a 和 b。- 每次满足条件，就更新
result，因为是从小到大遍历，最后的result必然是最大的。lcm_by_formula使用数学公式，避免重复计算。
这个方法逻辑清晰，适合初学者理解“什么是公约数”，但效率较低，时间复杂度为 O(min(a, b))。当数值很大时，会非常慢。
方法二：辗转相除法（欧几里得算法）——高效经典解法
如果说暴力枚举是“蚂蚁搬家”，那辗转相除法就是“闪电出击”。它由古希腊数学家欧几里得提出，是求 GCD 的标准方法，效率极高，时间复杂度仅为 O(log min(a, b))。
它的核心思想是：
两个数的最大公约数，等于其中较小数与两数相除余数的最大公约数。
举个例子：求 GCD(48, 18)
- 48 ÷ 18 = 2 余 12 → GCD(48, 18) = GCD(18, 12)
- 18 ÷ 12 = 1 余 6 → GCD(18, 12) = GCD(12, 6)
- 12 ÷ 6 = 2 余 0 → GCD(12, 6) = 6
当余数为 0 时，当前除数就是最大公约数。
#include <stdio.h>
// 求最大公约数：辗转相除法（欧几里得算法）
int gcd_by_euclidean(int a, int b) {
while (b != 0) { // 只要 b 不为 0，就继续循环
int temp = b; // 保存 b 的值
b = a % b; // b 更新为 a 除以 b 的余数
a = temp; // a 更新为原来的 b
}
return a; // 当 b 为 0 时，a 就是最大公约数
}
// 求最小公倍数：利用公式 LCM = (a * b) / GCD
int lcm_by_formula(int a, int b, int gcd) {
return (a * b) / gcd;
}
int main() {
int num1, num2;
printf("请输入两个正整数：");
scanf("%d %d", &num1, &num2);
int gcd = gcd_by_euclidean(num1, num2);
int lcm = lcm_by_formula(num1, num2, gcd);
printf("最大公约数为：%d\n", gcd);
printf("最小公倍数为：%d\n", lcm);
return 0;
}
代码说明：
while (b != 0)：循环条件，只要余数不为 0 就继续。temp = b：保存当前的除数，因为后面要更新 b。b = a % b：计算余数，作为下一轮的除数。a = temp：将原来的 b 赋给 a，相当于“移动”数值。- 最终当 b 为 0 时，a 就是 GCD。
这个方法虽然看起来简单，但背后的数学原理非常深刻。它把问题不断“缩小”，直到找到答案，是典型的“递归思想”的迭代实现。
方法三：递归实现辗转相除法（更优雅的写法）
如果你喜欢简洁的代码风格，递归版本会更让你心动。它把“重复调用自己”这一思想发挥到极致。
#include <stdio.h>
// 递归实现最大公约数：欧几里得算法
int gcd_recursive(int a, int b) {
// 递归终止条件：当 b 为 0 时，返回 a
if (b == 0) {
return a;
}
// 递归调用：GCD(a, b) = GCD(b, a % b)
return gcd_recursive(b, a % b);
}
// 求最小公倍数：利用公式
int lcm_by_formula(int a, int b, int gcd) {
return (a * b) / gcd;
}
int main() {
int num1, num2;
printf("请输入两个正整数：");
scanf("%d %d", &num1, &num2);
int gcd = gcd_recursive(num1, num2);
int lcm = lcm_by_formula(num1, num2, gcd);
printf("最大公约数为：%d\n", gcd);
printf("最小公倍数为：%d\n", lcm);
return 0;
}
代码说明：
if (b == 0)是递归的出口，防止无限调用。return gcd_recursive(b, a % b);是递归调用，把问题规模变小。- 递归版本更简洁，逻辑更清晰，但要注意栈溢出风险（不过对普通整数输入完全够用）。
实际案例与运行效果对比
我们来运行一个具体的例子：输入 48 和 18。
请输入两个正整数：48 18
最大公约数为：6
最小公倍数为：144
验证一下：
- GCD(48, 18) = 6 ✅
- LCM(48, 18) = (48 × 18) / 6 = 864 / 6 = 144 ✅
再试试大一点的数：1001 和 1003。
请输入两个正整数：1001 1003
最大公约数为：1
最小公倍数为：1004003
结果合理，说明两个数互质（只有公约数 1），所以 LCM 就是它们的乘积。
总结与建议
通过“C 练习实例16 – 最大公约数和最小公倍数”这一题目，我们不仅掌握了两种求 GCD 的核心方法——暴力枚举和辗转相除法，还理解了 GCD 与 LCM 之间的数学联系。
- 对初学者：建议先用暴力法理解概念，再学习辗转相除法。
- 对进阶者：推荐掌握递归版本，提升代码简洁性。
- 对面试者：一定要能手写欧几里得算法，这是高频考点。
记住：算法不是记忆，而是理解。当你能用一句话说清楚“为什么辗转相除法是对的”，你就真正掌握了它。
最后提醒一句：C 语言中整数除法和取模运算必须确保除数不为 0，建议在实际程序中加入输入验证，避免运行错误。
希望这篇文章能帮你把“最大公约数和最小公倍数”从“会写”变成“懂原理”，在编程路上走得更稳、更远。