【C语言】辗转相除法求最大公约数（详解）

辗转相除法求最大公约数

辗转相除法（又称欧几里德算法）是一种用于求解两个整数的最大公约数的方法。本文将使用C语言来实现辗转相除法，并对其原理进行解释。

辗转相除法的原理

辗转相除法的原理非常简单。假设有两个整数a和b，其中a > b。通过对a除以b求余数，得到余数r1。然后把b除以r1求余数，得到余数r2。如此重复，直到得到余数为0。那么这一系列的余数中的最后一个非零余数，就是a和b的最大公约数。即：

gcd(a, b) = gcd(b, r1) = gcd(r1, r2) = gcd(r2, r3) = … = gcd(r(n-1), rn) = gcd(rn, 0)

C语言实现

普通方法：

#includeint main(){int a = 0;int b = 0;int x = 0;scanf("%d %d", &a, &b);if (a < b){//交换两个元素x = a;a = b;b = x;}else{//如果进入else，就是a>b,x就会为0，循环就会结束x = a % b;while (x != 0){x = a % b;a = b;b = x;}printf("%d", a);}return 0;}

下面是使用C语言实现辗转相除法求最大公约数的代码示例：

#include // 辗转相除法求最大公约数int gcd(int a, int b) {if (b == 0){return a;}else{return gcd(b, a % b);}}int main() {int a = 0;int b = 0;printf("请输入两个整数：");scanf("%d %d", &a, &b);int result = gcd(a, b);printf("最大公约数为：%d", result);return 0;}

在上述代码中，我们使用递归的方式来实现辗转相除法。函数gcd接受两个整数a和b作为参数，如果b等于0，则返回a，否则递归调用自身，将b和a除以b取余数后的结果作为新的参数传入。直到b为0时，递归结束，返回a作为最大公约数。

在main函数中，我们从用户输入获取两个整数a和b，然后调用gcd函数求得最大公约数，最后将结果输出。

运行结果

假设我们输入两个整数12和18，运行上述代码后，将得到如下输出：

请输入两个整数：12 18最大公约数为：6

这说明12和18的最大公约数是6，验证了辗转相除法的正确性。

总结

辗转相除法是求解两个整数的最大公约数的一种常见算法。本文中，我们使用C语言实现了辗转相除法，并简要说明了其原理。通过实际的代码演示和运行结果，我们验证了辗转相除法的正确性。希望能够帮助到你理解该算法的实现过程。