c 语言辗转相除法

辗转相除法（又称欧几里得算法）是求两个非负整数的最大公约数的一种方法。以下是使用C语言实现辗转相除法的代码：

#include <stdio.h>

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

int main() {
    int a, b;
    printf("请输入两个非负整数：");
    scanf("%d%d", &a, &b);
    printf("%d和%d的最大公约数是：%d\n", a, b, gcd(a, b));
    return 0;
}

在上面的代码中，`gcd`函数通过递归调用自身来计算两个数的最大公约数，直到其中一个数为0时结束递归。在`main`函数中，我们通过用户输入获取两个数值，并调用`gcd`函数来计算它们的最大公约数，最后输出结果。

相关问题

c 语言求最小公倍数辗转

在C语言中，求两个整数的最小公倍数(LCM)的一种常见算法是通过辗转相除法，也称为欧几里得算法。这个算法基于数学原理：对于任意两个正整数a和b，它们的最大公约数(gcd)与a除以b的余数c之间的关系是gcd(a, b) = gcd(b, c)，当c为0时，b就是最大公约数，而a除以最大公约数就是最小公倍数。

以下是简单的C语言代码实现：

#include <stdio.h>

// 定义计算最大公约数的函数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

// 求最小公倍数的函数
int lcm(int a, int b) {
    int lcm_num = (a * b) / gcd(a, b);
    return lcm_num;
}

int main() {
    int num1, num2;
    printf("请输入两个整数: ");
    scanf("%d %d", &num1, &num2);
    int result = lcm(num1, num2);
    printf("两数的最小公倍数是: %d\n", result);
    return 0;
}

在这个程序中，首先计算两数的最大公约数，然后根据公式LCM(a, b) = |a*b| / GCD(a, b) 计算最小公倍数。用户会被提示输入两个数字，然后程序会输出他们的最小公倍数。

c 语言求最大公约数

在C语言中，我们可以使用辗转相除法来求两个数的最大公约数。下面是一个示例代码：

#include <stdio.h>

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

int main() {
    int a, b;
    printf("请输入两个整数：");
    scanf("%d %d", &a, &b);
    
    int result = gcd(a, b);
    printf("最大公约数是：%d\n", result);
    
    return 0;
}

在这段代码中，我们定义了一个名为gcd的函数，它接受两个整数a和b作为参数，并返回它们的最大公约数。在函数中，我们使用辗转相除法来求最大公约数。在main函数中，我们通过用户输入来获取两个整数，并调用gcd函数来求最大公约数。最后，我们将结果打印出来。

使用这个示例代码，我们可以在C语言中求两个数的最大公约数。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [蓝桥杯__省赛__第九届__C/C++__大学A组](https://blog.csdn.net/SongBai1997/article/details/88778038)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]