1. 题目描述

对于数 m 和数 n ，求 m 和 n 的最大公因数（Gcd）。
最大公因数是能同时整除二者的最大整数。

2. 题目分析

有公式：
当 m>=n 时，有Gcd（m，n）【也就是m，n的最大公因数】=Gcd（n，m%n），依照此种规律类推，当 Gcd 函数的第二个参数为0时，第一个参数就是答案。
比如：
Gcd(50,15)=Gcd(15,5)=Gcd（5,0）=5

3. 代码实现

#include <bits/stdc++.h>
using namespace std;
int gcd(int m,int n){
    if(n>m) swap(m,n); 
    while(n>0){
        int remainder=m%n;
        m=n;
        n=remainder;
    }
    return m;
}
int main(){
    int m=50;
    int n=15;
    cout<<gcd(50,15)<<endl;
}

4. 算法复杂度的分析

若M=1989，N=1590，则余数序列是399,393,6,3,0.我们将余数的大小近似于问题的规模，可以发现在一次迭代中余数并不按照一个常数因子递减。但是我们可以证明，在两次迭代后，余数最多是原始值的一半，故而迭代次数最多是
2logN=O（logN）。证明的详细过程可见书 P23下。

2020.1.5 更新
递归写法：欧几里得算法 1.5.cpp
上文中的是迭代的写法（也就是循环），然后这次写了一个递归的写法，虽然效率没有迭代高，但是可以作为参考来理解递归的思想吧。