c语言求最大公约数五种并写出算法分析
时间: 2024-09-14 17:04:42 浏览: 14
在C语言中,有多种方法可以求两个整数的最大公约数(Greatest Common Divisor,简称GCD)。以下是五种常见的算法:
1. **辗转相除法**(欧几里得算法):
算法步骤:
- a % b (a除以b的余数)
- 如果b等于0,那么a就是GCD;否则,将b替换为a,继续做除法直到余数为0。
```c
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
```
分析:时间复杂度为O(log min(a, b)),空间复杂度为O(1)。
2. **质因数分解法**:
将两个数分别分解成质因数乘积,然后找出公共的质因数,它们的连乘即为GCD。
```c
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
```
分析:时间复杂度取决于分解的速度,通常较慢,空间复杂度为O(1)。
3. **更相减损术**:
相互相减较小的那个数,直至两数相等,这个数就是最大公约数。
```c
int gcd(int a, int b) {
while (a != b) {
if (a > b)
a -= b;
else
b -= a;
}
return a;
}
```
分析:时间复杂度为O(max(a, b)),空间复杂度为O(1)。
4. **连续整除法**(也称短除法):
依次对a进行除法操作,每次除以b得到商和余数,直到余数为0。
```c
int gcd(int a, int b) {
while (a % b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return b;
}
```
分析:时间复杂度接近O(min(a, b)),空间复杂度为O(1)。
5. **中国剩余定理**(适用于大数场景,实际应用较少):
对于一组互质的整数,通过数学公式求解。这里不适合直接展示,因为C语言处理效率不高。
以上算法的选择取决于实际需求和数据规模,对于小范围内的数值,辗转相除法通常是最快的。