**C 语言中高效求最大公因数**339

最大公因数 (GCD) 是两个或多个整数中最大的公因子。在 C 语言中，计算 GCD 有多种方法。本文将介绍两种最常用的算法：辗转相除法和更相减损法，并提供 C 语言实现代码。本文还将讨论每种算法的复杂度和适用场景。

辗转相除法

辗转相除法是一种基于欧几里得算法的经典方法。该算法通过重复将较大的数字除以较小的数字并取余数来工作。余数将成为下一个较大的数字，而较小的数字保持不变。这种过程一直持续到余数为 0，此时较小的数字就是两数的 GCD。

以下是用 C 语言实现辗转相除法的代码：```c
int gcd_euclidean(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
```

更相减损法

更相减损法是另一种计算 GCD 的算法，它基于以下事实：两个奇数的 GCD 也是奇数，而两个偶数的 GCD 是 2 的倍数。该算法通过以下步骤来工作：
如果两个数字都是偶数，则它们的 GCD 为 2 乘以两个数字中较小的那一个的 GCD。
如果其中一个数字是偶数，另一个数字是奇数，则它们的 GCD 为该奇数的 GCD。
如果两个数字都是奇数且不相等，则它们的 GCD 为较小的那个减去较大那个的 GCD。

以下是用 C 语言实现更相减损法的代码：```c
int gcd_binary(int a, int b) {
if (a == 0 || b == 0) {
return 1;
}
if (a == b) {
return a;
}
if (a % 2 == 0 && b % 2 == 0) {
return 2 * gcd_binary(a / 2, b / 2);
} else if (a % 2 == 0) {
return gcd_binary(a / 2, b);
} else if (b % 2 == 0) {
return gcd_binary(a, b / 2);
}
if (a > b) {
return gcd_binary(a - b, b);
} else {
return gcd_binary(a, b - a);
}
}
```

复杂度和适用场景

辗转相除法的复杂度为 O(log(min(a, b))), 其中 min(a, b) 是 a 和 b 中较小的那个。更相减损法的复杂度为 O(log(min(a, b))), 在某些情况下，当 a 和 b 都很大时，它的复杂度可以更低。对于较小的数字，辗转相除法通常更快，而对于较大的数字，更相减损法更有效。

总结

C 语言中计算最大公因数有两种主要算法：辗转相除法和更相减损法。每种算法都有其优点和缺点，根据输入数字的大小选择最合适的算法很重要。本文提供了每种算法的 C 语言实现，以便于理解和使用。

2024-12-05

上一篇：C语言轻松输出两个数字

下一篇：如何在 C 语言中按降序输出三位整数