计算俩个整数m和n的最大公约数C语言

在C语言中计算两个整数m和n的最大公约数（Greatest Common Divisor，GCD），可以使用欧几里得算法（Euclidean Algorithm）。这个算法基于一个基本原理：两个整数a和b的最大公约数等于a除以b的余数c和b之间的最大公约数。

以下是C语言实现的一个简单版本：

#include <stdio.h>

// 函数声明，使用辗转相除法求最大公约数
int gcd(int m, int n);

int main() {
    int m, n;
    printf("请输入两个整数m和n: ");
    scanf("%d %d", &m, &n);
    int result = gcd(m, n);
    printf("它们的最大公约数是: %d\n", result);
    return 0;
}

// 辗转相除法求最大公约数
int gcd(int a, int b) {
    if (b == 0)
        return a; // 如果b为0，返回a作为结果
    else
        return gcd(b, a % b); // 否则递归地应用到b和a除以b的余数上
}

相关问题

c语言求两个正整数m和n最大公约数

C语言求两个正整数m和n最大公约数可以使用辗转相除法，也称为欧几里得算法。具体步骤如下：

1. 判断m和n的大小关系，使得m为较大值，n为较小值。

2. 用m除以n，得到余数r。

3. 若r为0，则n即为最大公约数。

4. 若r不为0，则令m=n，n=r，返回第2步。

C语言代码如下：

#include <stdio.h>

int gcd(int m, int n) {
    int r;
    while (n != 0) {
        r = m % n;
        m = n;
        n = r;
    }
    return m;
}

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

其中，函数gcd用于计算最大公约数，main函数用于输入两个正整数并输出它们的最大公约数。

求两个正整数m和n的最大公约数c语言时间复杂度是多少

求两个正整数m和n的最大公约数的时间复杂度可以用欧几里得算法来计算，其时间复杂度为O(log(min(m,n)))。具体实现可以使用递归或循环的方式。以下是使用递归的C语言代码示例：

int gcd(int m, int n) {
    if (n == 0) {
        return m;
    } else {
        return gcd(n, m % n);
    }
}

其中，m和n为要求最大公约数的两个正整数。