用两种方法求两个自然数m和n的最大公约数。 1 两种算法的伪码 2 c++代码的设计与实现

求两个自然数m和n的最大公约数（GCD，Greatest Common Divisor）可以采用欧几里得算法（Euclidean Algorithm），这是基于辗转相除法的思想。这里有两种常见的算法：

1. **算法一：辗转相除法**
- **伪码**（Euclid's algorithm）：

     function gcd(m, n):
         if n == 0:
             return m
         else:
             return gcd(n, m % n)

2. **算法二：更相减损术**
- **伪码**（Subtraction method, also known as Euclid's lemma in some cases）：

     function gcd(m, n):
         while n != 0:
             (m, n) = (n, m % n)
         return m

对于C++代码设计和实现，这里分别给出两种方法：

// 使用辗转相除法
#include <iostream>
int gcd(int m, int n) {
    if (n == 0)
        return m;
    else
        return gcd(n, m % n);
}

int main() {
    int m, n;
    std::cout << "Enter two numbers: ";
    std::cin >> m >> n;
    std::cout << "The GCD of " << m << " and " << n << " is: " << gcd(m, n) << "\n";
    return 0;
}

// 使用更相减损术
#include <iostream>

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

int main() {
    // ...（其余部分与辗转相除法版本相同）
}