22. 欧几里德算法（求最大公约数GCD）

算法内容：

求两个正整数 m , n 的最大公约数。

步骤：

1. 用 m 除以 n 得到余数 r 

2. 判断 r 是否为 0 ，如果为 0，那么说明最大公约数是 n，如果不为 0，则将 n 的值给 m ，将 r 的值给 n。直到 r 的值为 0 为止。

算法分解：

实例一：

假设 m = 10,  n = 5 。这种情况最简单，一眼就可以看出结果。首先，r = m % n = 10 % 5 = 0，算法结束，最大公约数为 5.

实例二：

假设 m = 15, n = 10。 这种情况需要计算多次。首先， r = m % n = 15 % 10 = 5 ≠ 0, 说明还需要继续计算。然后，令 m = 10, n = 5, 剩余步骤同实例一所示。

实例三：

假设 m = 5, n = 10。此处与上面两例的区别是，m 的值小于 n 的值，我们会产生一个疑问：在进行算法之前，是否需要将他们互换位置，以保持大的在前，小的在后呢？

首先， r = m % n = 5 % 10 = 5 ≠ 0 , 然后，令 m = 10, n = 5, 这样便回到了实例一。所以两个数的大小顺序，并不影响算法。

代码：

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

我们用了递归的手法，直接在内部互换各值，效果等同于显式赋值语句。

int main() {
    cout << "Enter two num : ";
    int a = 0, b = 0;
    cin >> a >> b;
    int result = GCD(a, b);

    cout << "The result is : " << result << endl;

    return 0;
}

运行上述代码，输入 10, 5, 结果为 5。