求m和n的最大公约数 c语言

以下是求m和n的最大公约数的C语言代码：

#include <stdio.h>

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

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

这个代码中的 `gcd` 函数使用了递归的方式来求最大公约数，如果 `n` 等于0，则返回 `m`，否则返回 `n` 和 `m % n` 的最大公约数。在 `main` 函数中，我们通过 `scanf` 函数来获取用户输入的两个整数，然后调用 `gcd` 函数来求它们的最大公约数，并将结果输出到控制台上。

相关问题

c语言求m和n最大公约数

以下是用C语言求m和n最大公约数的代码：

#include <stdio.h>

int main() {
    int m, n, t, r;
    printf("请输入两个数：\n");
    scanf("%d%d", &m, &n);
    if (m < n) {
        t = m;
        m = n;
        n = t;
    }
    while (n != 0) {
        r = m % n;
        m = n;
        n = r;
    }
    printf("最大公约数为：%d\n", m);
    return 0;
}

c语言求m和n最大公约数 5个方法

在C语言中，求两个整数m和n的最大公约数（GCD，Greatest Common Divisor），可以采用多种算法实现。以下是五种常见的求解方法：

1. **欧几里得算法**（Euclidean Algorithm）：
- 这是最常用的方法，基于数学原理：两数相除余数的GCD等于被除数和余数的GCD。不断将大数替换为余数，直到余数为0，此时的较小数即为GCD。

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

2. **辗转相减法**（Subtraction Method）：
- 当m > n时，m减去n得到新差值，然后继续这个过程，直到两数相等，该数值就是GCD。这种方法效率较低。

int gcd(int m, int n) {
    if (m < n)
        swap(m, n);
    while (n != 0) {
        m = m - n;
        swap(m, n);
    }
    return m;
}

3. **更相减损术**（Continued Subtraction）：
- 类似辗转相减，不过不是直接减而是反复交换并减小较大数，直到两数相等。

4. **质因数分解法**：
- 将m和n分别分解成质因数，然后找出公共的质因数，并将其乘积作为GCD。这种方法适合处理较大的数，但分解过程复杂。

int gcd(int m, int n) {
    for (int i = 2; i <= min(m, n); i++) {
        if (m % i == 0 && n % i == 0)
            return i;
    }
    return 1; // 如果都是质数，返回1
}

5. **扩展欧几里得算法**（Extended Euclidean Algorithm）：
- 此方法不仅能求出GCD，还能同时找到一组系数x和y使得ax + by = GCD(a, b)，这对于解决一些数学问题非常有用。

以上每一种方法都有其适用场景，根据实际需求选择最合适的方法。