c语言求最大公约数不会写代码？3种方法带实例轻松掌握

刚学 C 语言的朋友，是不是一碰到求最大公约数的题就发怵？老师在课上讲的方法听着好像懂了，可自己动手写代码就各种出错，要么逻辑理不清，要么运行结果不对。其实啊，求最大公约数没那么难，今天兔子哥就给大家分享 3 种简单方法，每种都带完整代码和步骤解析，就算是零基础也能看明白，一起往下看吧！

---

方法一：枚举法（穷举法）—— 最容易理解的笨办法

枚举法就是从 1 开始，一个个试哪个数能同时整除两个数，最大的那个就是最大公约数。比如求 12 和 18 的最大公约数，就从 1 试到 12，发现 6 是最大的能同时整除它们的数。
代码实例是这样的：
c运行

#include int main() {int a, b, i, gcd;printf("输入两个整数：");scanf("%d %d", &a, &b);// 先处理负数，转成正数if (a < 0) a = -a;if (b < 0) b = -b;// 从1循环到较小的那个数for (i = 1; i <= a && i <= b; i++) {// 如果i能同时整除a和b，就记录下来if (a % i == 0 && b % i == 0) {gcd = i;}}printf("最大公约数是：%d\n", gcd);return 0;}

这个方法的好处是特别好懂，新手一看就明白。但有个缺点，要是两个数很大，比如 10000 和 20000，就得循环一万次，有点慢。不过写作业的时候，数字一般都不大，用这个方法完全没问题。之前有个同学就靠这个方法，第一次就写出了正确代码，老师还夸他思路清晰呢。

---

方法二：辗转相除法（欧几里得算法）—— 又快又好用的方法

辗转相除法可比枚举法聪明多了，用大数除以小数得到余数，再用除数除以余数，一直这样算，直到余数是 0，这时候的除数就是最大公约数。
比如求 24 和 18：
24 ÷ 18 = 1 余 6
18 ÷ 6 = 3 余 0 → 所以 6 就是最大公约数
代码是这样写的：
c运行

#include int main() {int a, b, temp;printf("输入两个整数：");scanf("%d %d", &a, &b);// 处理负数if (a < 0) a = -a;if (b < 0) b = -b;// 辗转相除的核心循环while (b != 0) {temp = a % b; // 求余数a = b;        // 把除数变成被除数b = temp;     // 把余数变成除数}printf("最大公约数是：%d\n", a);return 0;}

很多人刚开始看不懂这个循环，其实你把每一步的 a 和 b 写在纸上就明白了。比如第一次循环后 a 变成 18，b 变成 6；第二次循环 a 变成 6，b 变成 0，循环结束，a 就是结果。这个方法速度特别快，就算是很大的数，几次循环就出结果了，兔子哥平时写代码最爱用这个。

---

方法三：更相减损术 —— 古老但实用的方法

这是咱们老祖宗发明的方法，用大数减小数，得到的差再和小数比较，重复相减，直到两个数相等，这个数就是最大公约数。
比如求 12 和 18：
18 - 12 = 6 → 现在变成 12 和 6
12 - 6 = 6 → 现在两个数都是 6，所以 6 是最大公约数
代码实例：
c运行

#include int main() {int a, b;printf("输入两个整数：");scanf("%d %d", &a, &b);// 处理负数if (a < 0) a = -a;if (b < 0) b = -b;// 只要两个数不相等就一直减while (a != b) {if (a > b) {a = a - b; // 大数减小数} else {b = b - a;}}printf("最大公约数是：%d\n", a);return 0;}

这个方法原理也很简单，就是不断缩小范围。不过它有个小问题，如果两个数相差很大，比如 10000 和 1，就得减很多次，比辗转相除法慢一点。但作为一种思路，了解一下也挺好，有时候换种方法思考，对理解编程很有帮助。

---

三种方法对比，该选哪个？

方法	优点	缺点	适合场景
枚举法	容易理解，代码简单	数字大时速度慢	新手练习，数字较小
辗转相除法	速度快，效率高	逻辑稍复杂	大多数情况，推荐使用
更相减损术	原理直观，历史悠久	极端情况速度慢	理解思路，拓展知识

有同学问，为什么处理负数的时候要转成正数？因为公约数一般都是正数，而且负数的取余或减法可能会出问题，转成正数能避免很多麻烦。试一下就知道，输入 - 12 和 18，转成正数后算出的结果和 12、18 是一样的。

---

兔子哥刚开始学的时候，也是先从枚举法入手的，虽然笨但能保证写对，慢慢理解了之后再学辗转相除法，就觉得顺多了。其实编程没有捷径，关键是多写多练，哪怕是照着抄一遍，也要自己走一遍流程。
这三种方法都不算难，选一种你能看懂的先练，熟练了再试试其他两种。写代码的时候别着急，一步一步来，就算出错了也没关系，看看哪里不对，改改就行。希望这篇文章能帮到不会写代码的你，下次碰到求最大公约数的题，肯定能轻松搞定！

标签： 欧几里得 零基础