C语言求最大公约数辗转相除法：原理、步骤与递归迭代两种写法

C语言求最大公约数辗转相除法（也称为欧几里得算法）是一种古老而有效的求两个整数的最大公约数（）的方法。该算法基于这样一个事实：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。辗转相除法通过反复将较大的数替换为较小的数，直到两数相等，此时它们的最大公约数就是这两个数。

原理：

假设有两个整数a和b，其中a > b。那么a和b的最大公约数和b与a - b（假设a - b > 0）的最大公约数是相同的。这是因为，如果某个数能同时整除a和b，那么它也能整除b和a - b。反之亦然。通过不断地用较小的数替换较大的数，直到两数相等，此时的数就是它们的最大公约数。

步骤：

1. 假设有两个整数a和b，其中a > b。

2. 如果b等于0，那么a就是最大公约数，算法结束。

3. 否则，将a替换为b，将b替换为a - b（或b - a，取决于哪个数更小）。

4. 重复步骤2和3，直到b等于0。

递归写法：

c

include

int gcd(int a, int b) {

if (b == 0)

return a;

else

return gcd(b, a % b);

}

int main() {

int num1, num2;

printf("输入两个整数: ");

scanf("%d %d", &num1, &num2);

printf("这两个整数的最大公约数是: %d", gcd(num1, num2));

return 0;

}

迭代写法：

c

include

int gcd(int a, int b) {

while (b != 0) {

int temp = b;

b = a % b;

a = temp;

}

return a;

}

int main() {

int num1, num2;

printf("输入两个整数: ");

scanf("%d %d", &num1, &num2);

printf("这两个整数的最大公约数是: %d", gcd(num1, num2));

return 0;

}

在这两个示例中，我们都定义了一个名为`gcd`的函数，它接受两个整数作为参数，并返回它们的最大公约数。在`main`函数中，我们从用户那里获取两个整数，并打印出它们的最大公约数。

递归版本使用递归调用`gcd`函数，直到b等于0，此时a就是最大公约数。迭代版本使用一个循环，每次迭代都将a替换为b，将b替换为a和b的余数，直到b等于0。

这两种方法都可以有效地求两个整数的最大公约数，而且都基于辗转相除法的原理。