C语言题解——最小公倍数的三种求法（含最大公约数）

🏆前言

最小公倍数是指能同时将两数整除的最小倍数，而最大公约数是则是能被两数同时整除的最小因数。最小公倍数有个特点，就是最小为两数中的较大值，最大为两数的乘积；最小公倍数则是最小为1，最大为两数中较小值（如果两数相同，那么最大公约数、最小公倍数是它们本身）🎉🎉🎉

简单了解这些基本知识后我们就可以进行求解了，求解的过程也很简单，中学数学足够了。

🏆正文

本文只介绍三种题解方法（其中一种解最大公约数还有问题），多理解记忆就能掌握。

🏃1.暴力试除法

暴力试除法指在范围内一个数一个数的试，如果找到符合条件的数，停止寻找即可，像这种逐个测试的方法一般称为穷举，缺点是慢，优点是数据不容易出错。

//1.暴力试除法 #include<stdio.h> int the_max(int a, int b) { //获取两数中的较大数 return a > b ? a : b; } int the_min(int a, int b) { //获取两数中的较小数 return a < b ? a : b; } int main() { int a = 0; int b = 0; printf("请输入两个数字:>"); scanf("%d %d", &a, &b); //先求最小公倍数 int min = the_max(a,b);//定义变量存储 for (; min <= a * b; min++) { if (min % a == 0 && min % b == 0) break; } printf("%d %d两数的最小公倍数为%d\n", a, b, min); //最大公约数，原理基本相同 int max = the_min(a, b);//定义变量存储 for (; max > 0; max--) { if (a % max == 0 && b % max == 0) break; } printf("%d %d两数的最大公约数为%d\n", a, b, max); return 0; }//暴力试除法，效率较低

暴力试除法过于暴力，纯属是以时间换效率，如果想要高效率，这种方法肯定是不可取的！

🏃‍♂️2.优雅试除法

优雅试除法不同于暴力试除法，它采用倍数的巧妙关系，绕过了很多无意义的循环，从而提升了效率。求最小公倍数时扩大倍数没问题，但求最大公约数时会存在一些问题，我已经做了一些优化，但在某些数据上这种方法求最大公约数还是有问题！

//2.优雅试除法_效率更高 //经过测试，这种方法虽然优雅 //但在求最大公约数时可能会出错 //比如 2048与408，其他方法是8，而这是16！ //没有最优的方法，只有最灵活的方法！！！ #include<stdio.h> int main() { int a = 0; int b = 0; printf("请输入两个数字:>"); scanf("%d %d", &a, &b); int ret = 1;//效率提高的关键变量 while ((a * ret) % b) ret++; printf("%d %d两数的最小公倍数为%d\n", a, b, a*ret); int tmp = 1;//同样是重要变量 //测试发现，当先输入奇数，再输入偶数时会出错 //以及都是偶数时，前数字较大会出错 //原因：没有确定大值与小值 int min = a < b ? a : b;//找出较小值 int max = a > b ? a : b;//找出较大值 while (max%(min/tmp)) tmp++; printf("%d %d两数的最大公约数为%d\n", a, b, min / tmp); return 0; }

优雅试除法求最小公倍数完全没有问题！但求最大公约数要慎重，有用的方法才是好方法！

🏃‍♀️3.辗转相除法（欧几里得算法）

欧几里得，数学大佬，琢磨出来辗转相除求最大公约数这个巧妙方法，具体的数学原理我们不必去研究，只需要知道如何用C语言翻译就行了。

**几何大师-欧几里得图片来源：数学史话之几何大师欧几里得！|几何原本|欧几里得|几何学_新浪新闻 (sina.com.cn)**

//3.辗转相除法（欧几里得算法） #include<stdio.h> int main() { int a = 0; int b = 0; printf("请输入两个数字:>"); scanf("%d %d", &a, &b); int a1 = a;//辗转相除会改变值 int b1 = b;//因此需要替身 int tmp = 0; while (b1) { //辗转相处求出最大公约数 tmp = a1 % b1; a1 = b1; b1 = tmp; //此时a1就是最大公约数 } // a * b / a1 = 最小公倍数 printf("%d %d两数的最小公倍数为%d\n", a,b,a*b/a1); printf("%d %d两数的最大公约数为%d\n", a, b, a1); return 0; }

辗转相除法非常好用！欧几里得是真的强，将效率提供升到了一个新的高度。理解了这种算法，以后求最大公约数和最小公倍数简直是信手拈来，十分轻松！

🏆总结

最小公倍数与最大公约数是C语言学习前期十分合适的算法，逻辑比较简单，代码量也很小，只需要使用分支与循环语句，做好条件判断，程序还是很好写出来的。关于其他解法可以去看看别的博主的文章，找到适合自己的求解方法，就像语言一样，没有最好的，只有最合适的！🎊🎊🎊

如果你觉得本文写的还不错的话，期待留下一个小小的赞👍，你的支持是我分享的最大动力！

如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正！

今天的文章 C语言题解——最小公倍数的三种求法（含最大公约数）分享到此就结束了，感谢您的阅读。

C语言题解——最小公倍数的三种求法（含最大公约数）

🏆前言

🏆正文

🏃1.暴力试除法

🏃‍♂️2.优雅试除法

🏃‍♀️3.辗转相除法（欧几里得算法）

🏆总结

相关推荐