欧几里得算法（辗转相除法）

今天楚学长在讲解算法题的时候，向我们介绍了欧几里德算法（Euclidean algorithm），又名辗转相除法， 是求两个正整数最大公约数的算法。

非递归实现：

long long gcd(long long m,long long n)
{
　　long long r;
　　do{
　　　　r = m % n;
　　　　m = n;
　　　　n = r; 
　　　}while(r!=0);
　　　return m;
}

递归实现：

long long gcd(long long m,long long n)
{　　
　　return n==0?m:gcd(n,m%n);
}

优点：
① 不必考虑m与n的大小问题。
② 利用欧几里德算法，求出两个正整数的最大公约数后，就能得出它们的最小公倍数：最小公倍数 = （正整数1 * 正整数2） / 最大公约数