c语言求最大公约数

发布时间：2025-10-09 | 来源：互联网转载和整理

最大公约数（Greatest Common Divisor，简称GCD）是指两个或多个数中最大的能够同时整除它们的数。求最大公约数在算法中是一个非常重要的问题，因为它是许多其他算法的基础。在C语言中，求最大公约数有多种方法，其中最常见的方法是使用辗转相除法。

辗转相除法，也叫欧几里得算法，是一种求最大公约数的简单有效的方法。它的基本思想是：用较大的数除以较小的数，再用余数去除较小的数，如此反复，直到余数为0为止。最后的除数就是最大公约数。具体实现如下：

```c

int gcd(int a, int b) {

int r;

while (b != 0) {

r = a % b;

a = b;

b = r;

}

return a;

}

```

上述代码中，a和b分别为输入的两个整数，r为余数。在while循环中，如果b不为0，则将a对b取余，将余数赋值给r，然后将b赋值给a，将r赋值给b。这样，每次循环都将b赋值为a%b，直到b为0为止。最后返回的a就是最大公约数。

辗转相除法的时间复杂度为O(logn)，其中n为两个整数中较小的那个数。因此，该算法的效率非常高，可以在很短的时间内求出最大公约数。

除了辗转相除法，还有其他一些求最大公约数的方法，例如质因数分解法、更相减损法等。但是，这些方法的时间复杂度都比较高，不如辗转相除法高效。

总之，求最大公约数是一个非常基础的问题，也是算法中的一个重要问题。在C语言中，使用辗转相除法可以很快地求出最大公约数。