c语言求最大公约数辗转相除法代码及步骤解析

写 C 语言作业的时候，是不是碰到过求最大公约数的题？课本上提到的辗转相除法，看着文字描述挺简单，可真要写成代码，要么逻辑理不清，要么循环条件写错，运行结果总不对。其实啊，辗转相除法是求最大公约数最常用的方法，只要搞懂它的原理，代码写起来一点都不难。今天兔子哥就一步步给你讲清楚，从原理到代码实现，再到常见错误，保证新手也能看明白，一起往下看吧！

---

先搞懂：最大公约数和辗转相除法到底是啥？

最大公约数，就是两个数都能被整除的最大的数。比如 12 和 18，能同时整除它们的数有 1、2、3、6，所以最大公约数是 6。
那辗转相除法又是啥？它还有个名字叫欧几里得算法，是几千年前就有的方法。原理特简单：两个数的最大公约数，等于其中较小的数和两数相除余数的最大公约数。要是余数是 0 了，那除数就是最大公约数。
举个例子，求 24 和 18 的最大公约数：
第一步，24 除以 18，商 1 余 6；
第二步，用 18 除以 6，商 3 余 0；
余数是 0 了，所以 6 就是 24 和 18 的最大公约数。
是不是很直观？这就是辗转相除法的妙处，不用把所有因数列出来，几步就能算出结果。

---

怎么用 C 语言实现辗转相除法？分步骤写代码

知道了原理，写代码就有方向了。咱们分步骤来，先理清楚逻辑，再写代码。
第一步：确定函数参数和返回值
需要两个整数，返回它们的最大公约数，所以函数可以定义成int gcd(int a, int b)。
第二步：处理特殊情况
要是其中一个数是 0，最大公约数就是另一个数（比如 a=0，b=5，最大公约数是 5）。
第三步：实现辗转相除的循环
用循环不断求余数，直到余数为 0。循环里每次用除数当新的被除数，余数当新的除数。
完整代码是这样的：
c运行

#include // 求最大公约数的函数int gcd(int a, int b) {int temp;// 处理负数，因为公约数一般取正数if (a < 0) a = -a;if (b < 0) b = -b;// 确保a大于等于b，方便计算（也可以不用这步，后面会处理）if (a < b) {temp = a;a = b;b = temp;}// 辗转相除的核心循环while (b != 0) {temp = a % b; // 求余数a = b;        // 除数变被除数b = temp;     // 余数变除数}return a; // 余数为0时，被除数就是最大公约数}int main() {int num1, num2;printf("请输入两个整数：");scanf("%d %d", &num1, &num2);printf("最大公约数是：%d\n", gcd(num1, num2));return 0;}

---

代码里的关键步骤，你可得注意

1. 处理负数：要是输入负数，比如 - 12 和 18，最大公约数还是 6。所以先把负数转成正数，用if (a < 0) a = -a;就行。
2. 交换 a 和 b 的值：确保 a 比 b 大，这样第一次求余更顺。其实不交换也能算，因为如果 a 比 b 小，a % b的结果就是 a，下一轮循环会自动交换。
3. 循环结束条件：必须是b != 0，因为当 b 变成 0 时，a 就是我们要的结果。要是写成a != 0，循环就停不下来了。

比如输入 18 和 24，即使不交换，第一次循环：
a=18，b=24，temp=18%24=18；
a 变成 24，b 变成 18，接下来就和之前的步骤一样了。

---

常见错误及解决办法，新手别踩坑

错误一：没处理负数，导致结果出错
输入 - 8 和 12，要是没转成正数，-8 % 12的结果是 - 8，循环下去会得到负数，这显然不对。解决办法就是先把 a 和 b 都转成正数。
错误二：循环条件写错，程序卡死
把while (b != 0)写成while (a != 0)，当 b 变成 0 后，a 的值不变，循环会一直跑，程序就卡死了。记住，循环条件一定是判断除数（b）是否为 0。
错误三：交换值时逻辑出错
交换 a 和 b 的时候，要是写成a = b; b = a;，这样 a 和 b 会变成同一个值，就错了。必须用临时变量 temp，先存 a 的值，再赋值。

---

不用辗转相除法会怎样？

求最大公约数还有别的方法，比如枚举法（从 1 到较小的数，找能同时整除的最大数），但效率太低了。比如求 10000 和 9999 的最大公约数，枚举法要循环一万次，而辗转相除法几步就搞定。
兔子哥之前做作业的时候，一开始用的枚举法，老师说 “数据大的时候程序会很慢”，后来改成辗转相除法，不仅代码简洁，运行也快多了。所以啊，知道原理还不够，选对方法很重要。

---

其实辗转相除法的代码不长，但逻辑得理清楚。你可以多试几个数，比如 25 和 15、7 和 5，一步步跟着代码走，看看变量怎么变的，很快就能理解。写代码的时候，处理好负数和循环条件，基本就不会出错了。
刚开始可能觉得绕，但多写几遍就会发现，这方法真的很巧妙。下次再碰到求最大公约数的题，不妨试试这个方法，又快又准。希望今天讲的这些能帮到你，有问题的话多调试几次，慢慢就熟练了！

标签： 欧几里得 大于等于