c语言求最大公约数和最小公倍数完整实现方法

写 C 语言作业的时候，是不是经常碰到既要算最大公约数又要算最小公倍数的题？比如让你输入两个数，先求出它们的最大公约数，再用这个结果算最小公倍数。新手往往会卡在两步的衔接上，要么算错了最大公约数，要么不知道怎么用它求最小公倍数，最后代码改来改去还是不对。今天兔子哥就把这两个问题放在一起讲，从原理到完整代码，一步步教你怎么实现，保证看完就有思路，一起往下看吧！

---

先弄明白：最大公约数和最小公倍数到底啥关系？

最大公约数就是两个数都能被整除的最大的数，比如 12 和 18，最大公约数是 6。那最小公倍数呢，就是两个数的公共倍数里最小的那个，12 和 18 的最小公倍数是 36。
这俩东西看着没关系，其实联系大了。有个公式特别好用：两个数的乘积，等于它们的最大公约数乘以最小公倍数。也就是说，最小公倍数 = （两个数的乘积）÷ 最大公约数。比如 12×18=216，216÷6=36，正好是它们的最小公倍数。
虽然这个公式用起来很方便，但新手常犯的错是，算完乘积直接除以最大公约数，却忘了乘积可能太大，超过整数的范围。比如两个很大的数相乘，结果可能溢出，导致最后结果不对。不过话说回来，一般的作业题里，数字不会大到溢出，先用这个方法应付考试和作业是没问题的。

---

求最大公约数，还是辗转相除法最实用

求最大公约数的方法有好几种，比如枚举法（一个个试）、辗转相除法。枚举法虽然好理解，但数字大的时候特别慢。辗转相除法就快多了，步骤也简单。
辗转相除法的步骤是这样的：

1. 用较大的数除以较小的数，得到余数；
2. 把刚才的除数当成新的被除数，余数当成新的除数；
3. 重复上面的步骤，直到余数是 0 为止，这时候的除数就是最大公约数。

用 C 语言写出来是这样的：
c运行

// 求最大公约数的函数int getGCD(int a, int b) {int temp;// 处理负数，让它们变成正数if (a < 0) a = -a;if (b < 0) b = -b;// 辗转相除的核心循环while (b != 0) {temp = a % b; // 求余数a = b;        // 除数变被除数b = temp;     // 余数变除数}return a;}

这个函数里，先把负数转成正数，因为公约数一般都是正数。循环里每次更新 a 和 b 的值，直到 b 变成 0，a 就是我们要的结果。

---

有了最大公约数，怎么求最小公倍数？

知道了最大公约数，求最小公倍数就简单了，直接用刚才说的公式：最小公倍数 = （a×b）÷ 最大公约数。不过这里有个小细节，最好先算除法再算乘法，比如写成（a÷ 最大公约数）×b，这样能减少溢出的可能。
比如 a=12，b=18，最大公约数是 6，（12÷6）×18=2×18=36，和直接算 12×18÷6 结果一样，但更安全。
对应的函数可以这样写：
c运行

// 求最小公倍数的函数，需要用到最大公约数int getLCM(int a, int b, int gcd) {// 先判断gcd是否为0，避免除以0的错误if (gcd == 0) {return 0; // 要是两个数都是0，这里返回0}// 先除后乘，减少溢出风险return (a / gcd) * b;}

这里要注意，必须先判断最大公约数是不是 0，不然可能会出现除以 0 的错误，程序就崩了。

---

完整代码示例，直接能用

把上面两个函数合起来，再加上主函数，就能实现从输入到输出的完整功能了：
c运行

#include // 求最大公约数int getGCD(int a, int b) {int temp;if (a < 0) a = -a;if (b < 0) b = -b;while (b != 0) {temp = a % b;a = b;b = temp;}return a;}// 求最小公倍数int getLCM(int a, int b, int gcd) {if (gcd == 0) {return 0;}return (a / gcd) * b;}int main() {int num1, num2;int gcd, lcm;printf("请输入两个整数：");scanf("%d %d", &num1, &num2);gcd = getGCD(num1, num2);lcm = getLCM(num1, num2, gcd);printf("最大公约数是：%d\n", gcd);printf("最小公倍数是：%d\n", lcm);return 0;}

试一下输入 12 和 18，会输出 6 和 36，完全正确。输入 0 的话，比如 0 和 5，最大公约数是 5，最小公倍数是 0，这也是对的。

---

新手容易踩的坑，你可得注意

1. 忘了处理负数：如果输入 - 12 和 18，不转成正数的话，辗转相除会出问题，结果可能是负数或者错的。所以一定要先把 a 和 b 变成正数。
2. 直接用 a×b 除以最大公约数：比如 a 和 b 都是 100000，乘积就是 10000000000，可能超过 int 的范围（int 一般最大是 20 多亿），导致结果出错。用（a÷gcd）×b 更安全。
3. 没判断最大公约数为 0 的情况：如果两个数都是 0，最大公约数是 0，这时候算最小公倍数就会除以 0，程序直接崩溃。所以函数里必须加判断。

至于为什么 “两个数的乘积等于最大公约数乘最小公倍数” 这个公式总能成立，具体的数学证明我记不太清了，可能需要查一下数论的资料。但用起来是没问题的，至少在整数范围内，我还没碰到过例外。

---

兔子哥觉得，这两个问题放在一起学，比单独学一个更有效。因为它们本来就有关系，掌握了最大公约数的求法，最小公倍数就是顺手的事。写代码的时候，最好把两个功能分成不同的函数，这样看起来清楚，也方便以后复用。
平时练习的时候，可以多试试不同的数，比如正数、负数、包含 0 的情况，看看代码会不会出错。练多了就会发现，其实不难，关键是把辗转相除法的逻辑和两个数的关系搞明白。希望今天讲的这些能帮到你，有问题多调试几次，慢慢就熟练了！

标签： 不知道 是不是