C语言求最大公约数

在数学中，最大公约数（Greatest Common Divisor，简称GCD）是指两个或多个整数的公有约数中最大的一个数。在计算机领域中，求最大公约数是一种常见的数学问题，常常用于计算机算法中。

在本文中，我们将以C语言为基础，介绍如何求解两个数的最大公约数。

欧几里得算法

欧几里得算法，也叫辗转相除法，是求两个数的最大公约数的一种算法。该算法是基于如下原理：两个整数的最大公约数等于其中较小的那个数和两数的差的最大公约数。

例如，对于两个整数a和b，它们的最大公约数等于a和b的余数r，以及b和r的最大公约数。简单来说，就是a和b的余数r作为新的b，原来的b作为新的a，不断地取模运算，直到余数为0为止，此时a就是原来的a和b的最大公约数。

C语言实现：

```

#include

int gcd(int a, int b) {

int r;

while(b != 0) {

r = a % b;

a = b;

b = r;

}

return a;

}

int main() {

int a, b, result;

printf("输入两个整数：\n");

scanf("%d %d", &a, &b);

result = gcd(a, b);

printf("两个数的最大公约数为：%d\n", result);

return 0;

}

```

其中，函数gcd()即为欧几里得算法的实现。程序首先接受两个整数a和b，然后不断地做模运算并更新a和b的值，直到b等于0为止，此时a就是两个整数的最大公约数。

扩展欧几里得算法

扩展欧几里得算法可以求解两个数的最大公约数，并得到一个数的质数系数。该算法采用递归的方式，不仅可以用于求最大公约数，还可以用于求解线性不等式的一般解。

例如，对于线性不等式ax+by=c，如果我们知道了x和y的最小整数解x0和y0，那么该不等式的一般解为：

x = x0 + kb/gcd(a, b)

y = y0 - ka/gcd(a, b)

其中k为任意整数。

C语言实现：

```

#include

int extgcd(int a, int b, int *x, int *y) {

if(b == 0) {

*x = 1;

*y = 0;

return a;

}

int d = extgcd(b, a%b, x, y);

int t = *x;

*x = *y;

*y = t - a/b * (*y);

return d;

}

int main() {

int a, b, x, y, result;

printf("输入两个整数：\n");

scanf("%d %d", &a, &b);

result = extgcd(a, b, &x, &y);

printf("两个数的最大公约数为：%d\n", result);

printf("一个数的质数系数为：(%d) * %d + (%d) * %d = %d\n", a, x, b, y, result);

return 0;

}

```

函数extgcd()即为扩展欧几里得算法的实现。模仿欧几里得算法的递归式，该函数采用递归方式，不断地更新x和y的值，最后返回a和b的最大公约数。

与欧几里得算法不同的是，扩展欧几里得算法返回的不仅是a和b的最大公约数，还可以得到一个数的质数系数。

总结

本文中，我们介绍了两种主要的求解最大公约数的方法：欧几里得算法和扩展欧几里得算法。在C语言中，只要掌握了基本的算法思想和语法，我们就能够轻松求解两个数的最大公约数和一个数的质数系数。

当然，还有其他的算法可以求解最大公约数，例如辗转相减法和质因数分解法等。不过，在实际编程中，欧几里得算法和扩展欧几里得算法已经足够使用，我们不必过分纠结于其它算法的复杂性和效率问题。