[教程]掌握C语言求辗转相除法，轻松解决最大公约数问题

引言辗转相除法（也称为欧几里得算法）是一种高效求解最大公约数（Greatest Common Divisor，GCD）的方法。在C语言中，我们可以通过编写一个简单的函数来实现这一算法。本文将详细介绍如...

引言

辗转相除法（也称为欧几里得算法）是一种高效求解最大公约数（Greatest Common Divisor，GCD）的方法。在C语言中，我们可以通过编写一个简单的函数来实现这一算法。本文将详细介绍如何在C语言中实现辗转相除法，并举例说明其应用。

1. 基本原理

辗转相除法的原理如下：

• 如果两个数a和b（a > b）的最大公约数是d，那么a和b的差（a - b）也能被d整除。
• 因此，我们可以用较大的数除以较小的数，然后用余数替换较大的数，重复这个过程，直到余数为0。此时，较小的数就是两个数的最大公约数。

2. C语言实现

下面是一个C语言函数，用于实现辗转相除法：

#include 
// 函数声明
int gcd(int a, int b);
int main() { int num1, num2, result; // 输入两个数 printf("请输入两个整数（用空格分隔）："); scanf("%d %d", &num1, &num2); // 调用gcd函数 result = gcd(num1, num2); // 输出结果 printf("最大公约数是：%d\n", result); return 0;
}
// 函数定义
int gcd(int a, int b) { int temp; while (b != 0) { temp = b; b = a % b; a = temp; } return a;
}

在上面的代码中，gcd函数实现了辗转相除法。main函数用于接收用户输入的两个整数，并调用gcd函数计算它们的最大公约数。

3. 代码解释

• gcd函数接收两个整数a和b作为参数。
• 使用while循环实现辗转相除法。在循环中，将b的值赋给临时变量temp，然后计算a % b的余数，并将余数赋给b。最后，将temp的值赋给a。
• 当b为0时，退出循环，此时a即为两个数的最大公约数。

4. 应用示例

以下是一个使用辗转相除法求解最大公约数的示例：

#include 
// 函数声明
int gcd(int a, int b);
int main() { int num1 = 48, num2 = 18; int result; // 调用gcd函数 result = gcd(num1, num2); // 输出结果 printf("%d和%d的最大公约数是：%d\n", num1, num2, result); return 0;
}
// 函数定义
int gcd(int a, int b) { int temp; while (b != 0) { temp = b; b = a % b; a = temp; } return a;
}

在上面的代码中，我们分别计算了48和18的最大公约数，结果为6。

总结

本文介绍了如何在C语言中实现辗转相除法，并举例说明了其应用。通过学习本文，读者可以轻松掌握求解最大公约数的方法。