c语言求最大公约数效率最高的算法

写 C 语言代码的时候，谁不希望自己的程序跑得飞快呢？尤其是处理大数据的时候，一个效率高的算法能省不少时间。就说求最大公约数吧，方法不止一种，但哪种才算效率最高的？新手可能觉得只要能算出结果就行，可真碰到大数字，比如几万、几十万的数，效率低的算法能卡到你怀疑人生。今天老周就跟大家好好聊聊，求最大公约数效率最高的算法到底是啥，怎么用 C 语言实现，看完你就知道该选哪种了，一起往下看吧！

---

先说说常见算法的效率坑

咱们先看看平时可能用到的方法，它们的效率到底差在哪。
最容易想到的是枚举法，就是从 1 开始一个个试，看看哪个数能同时整除两个数。这种方法对付小数字还行，比如 100 以内的数，眨眼就出结果。可要是算两个 100000 的数，就得循环 10 万次，这速度谁受得了？之前有个同学用枚举法写作业，输入了两个大数字，程序跑了半分钟都没出结果，还以为是代码写错了，其实就是效率太低。
再说说更相减损术，这是老祖宗传下来的方法，用大数减小数，反复减直到两数相等。听起来挺简单，但如果两个数相差特别大，比如 100000 和 1，就得减 10 万次，比枚举法还费劲。所以啊，这两种方法虽然好理解，但效率真不咋地，只能应付应付小数字。

---

效率之王：辗转相除法（欧几里得算法）

要说求最大公约数效率最高的，那还得是辗转相除法，也叫欧几里得算法。这方法两千多年前就有了，能流传这么久，肯定有它的道理。
它的原理特简单：两个数的最大公约数，等于其中较小的数和两数相除余数的最大公约数。就拿 24 和 18 来说，24 除以 18 余 6，再用 18 除以 6 余 0，这时候 6 就是最大公约数。你看，就两步就算出来了，多快！
用 C 语言写出来是这样的：
c运行

#include #include  // 后面要用abs()处理负数int gcd(int a, int b) {a = abs(a); // 处理负数，转成正数b = abs(b);while (b != 0) {int temp = a % b;a = b;b = temp;}return a;}int main() {int num1, num2;printf("输入两个整数：");scanf("%d %d", &num1, &num2);printf("最大公约数：%d\n", gcd(num1, num2));return 0;}

为啥说它效率高？因为每次计算都是用余数来缩小范围，循环次数特别少。就算是两个很大的数，比如 10 亿级别的，最多也就循环几十次，比枚举法和更相减损术快太多了。群里有个做数值计算的朋友说，他们处理大量数据时，必用辗转相除法，从来没出过效率问题。

---

还能更快？试试 Stein 算法（二进制优化）

辗转相除法已经很快了，但还有一种叫 Stein 算法的，是对它的优化，在处理二进制数时更有优势。
Stein 算法的巧妙之处在于，它用移位操作代替了取余，计算机处理移位可比取余快多了。具体步骤是这样的：

1. 如果两个数都是偶数，就都除以 2（右移 1 位），并记录除以 2 的次数；
2. 如果一个是偶数一个是奇数，偶数除以 2；
3. 如果都是奇数，就用大数减小数，重复上面的步骤；
4. 最后把结果乘以之前记录的 2 的次数。

代码大概是这样的：
c运行

int stein_gcd(int a, int b) {if (a == 0) return b;if (b == 0) return a;a = abs(a);b = abs(b);int shift = 0;// 找两个数的公共因子2while (((a | b) & 1) == 0) {a >>= 1;b >>= 1;shift++;}// 把a变成奇数while ((a & 1) == 0) {a >>= 1;}do {// 把b变成奇数while ((b & 1) == 0) {b >>= 1;}// 保证a <= b，然后用b减aif (a > b) {int temp = a;a = b;b = temp;}b -= a;} while (b != 0);// 乘以之前的公共因子2return a << shift;}

Stein 算法在理论上比辗转相除法略快，尤其是处理非常大的数时。不过对于一般的应用，两者的差距感觉不明显。有同学测试过，用两个 100 位的大整数计算，Stein 算法确实能快个几毫秒，但平时写代码，辗转相除法已经足够用了。

---

两种高效算法对比，该怎么选？

算法	优点	缺点	适用场景
辗转相除法	代码简单，理解容易，效率高	取余操作对大数字稍慢	大多数情况，推荐新手用
Stein 算法	移位操作更快，适合二进制环境	代码稍复杂，步骤多	处理超大数字，对效率要求极高

老周个人觉得，平时写代码用辗转相除法就够了，又简单又高效，不容易出错。Stein 算法虽然更快一点，但代码复杂，新手容易写错，除非真的需要极致优化，否则没必要折腾。

---

可能有人会问，既然辗转相除法这么好，为啥还要学其他方法？其实啊，了解不同算法的效率差异，能帮你养成写高效代码的习惯。刚开始学编程的时候，我也觉得 “能跑就行”，后来做项目处理大量数据，才明白效率有多重要，一个好的算法能让程序快几十倍。
所以啊，求最大公约数，优先用辗转相除法，简单又高效。要是你想挑战一下自己，或者确实需要处理超大数字，再试试 Stein 算法。多写几遍代码，对比一下它们的运行时间，你就知道哪个更适合你了。希望这些能帮到你，写出又快又好的代码！

标签： 欧几里得 大数字