辗转相除法用c语言实现

在 C 语言中，辗转相除法（也叫欧几里得算法）通常用于计算两个整数的最大公约数（GCD）。以下是其基本实现：

#include <stdio.h>

// 定义一个辅助函数，计算较小数除较大数的余数
int gcd_helper(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd_helper(b, a % b);
}

// 主函数计算 GCD
int main() {
    int num1, num2;
    printf("请输入两个整数：");
    scanf("%d %d", &num1, &num2);

    // 使用递归的方式计算 GCD
    int result = gcd_helper(num1, num2);
    
    printf("两数的最大公约数是：%d\n", result);

    return 0;
}

在这个代码中，`gcd_helper` 函数是递归的，当 `b` 等于零时，返回 `a` 作为结果；否则，它会继续调用自身，将 `b` 和 `a` 除以 `b` 的余数作为新的参数。当输入的两个数足够小以至于 `b` 变为零时，递归结束，此时 `a` 就是最大公约数。

相关问题

辗转相除法代码c语言

辗转相除法，也称欧几里得算法，是一种古老的计算两个正整数最大公约数（Greatest Common Divisor, GCD）的方法。在C语言中，你可以通过递归或者循环的方式实现它。以下是简单的循环版本的代码示例：

#include <stdio.h>

// 定义函数计算gcd
int gcd(int a, int b) {
    while (b != 0) {
        int temp = a % b; // 计算余数
        a = b;         // 更新a为b
        b = temp;       // 更新b为余数
    }
    return a; // 返回最后的商作为最大公约数
}

int main() {
    int num1, num2;
    printf("请输入两个正整数：");
    scanf("%d %d", &num1, &num2);

    int result = gcd(num1, num2);
    printf("这两个数的最大公约数是：%d\n", result);

    return 0;
}

在这个代码中，`gcd()` 函数不断将较大的数除以较小的数并取余，直到余数为0，此时较小的数就是两数的最大公约数。

辗转相除法c语言递归

好的，以下是辗转相除法的C语言递归实现：

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

这个函数接受两个整数参数a和b，返回它们的最大公约数。如果b等于0，则a就是最大公约数；否则，递归调用gcd函数，传入参数b和a%b。