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)，这对于解决一些数学问题非常有用。

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

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

＊＊＊和n的最大公约数的例子：

1.辗转相除法

#include <stdio.h>
int main() {
    int m, n, r, t;
    scanf("%d %d", &m, &n);
    printf("%d和%d的最大公约数是\n", m, n);
    if (m < n) {
        t = m;
        m = n;
        n = t;
    }
    while (m % n != 0) {
        r = m % n;
        m = n;
        n = r;
    }
    printf("%d\n", n);
    return 0;
}

2.辗转相减法

#include <stdio.h>
int main() {
    int a, b, c, d, f;
    printf("请输入两个正整数：");
    scanf("%d%d", &a, &b);
    d = a, f = b; //用来保留原来输入的数据
    if (a == 0 || b == 0) {
        printf("输入的数据有误！");
    } else {
        while (a != b) {
            if (a > b) {
                a = a - b;
            } else {
                b = b - a;
            }
        }
        printf("%d和%d的最大公约数为：%d", d, f, a); //这里最大公约是a
    }
    return 0;
}