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

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