作者：不详 来源：互联网 酷勤网收集 2008-02-29
摘要
欧几里德算法也就是辗转相除法，有着2000年的历史了。欧几里德算法依据的算法理论是一个定理：gcd(a,b) = gcd(b,a mod b)。
欧几里德算法也就是辗转相除法，有着2000年的历史了。欧几里德算法依据的算法理论是一个定理：gcd(a,b) = gcd(b,a mod b)。
实现源码为：
|
//递归实现 int gcd(int m,int n) { if (m < n) { int tmp = m; m = n; n = tmp; } if (n == 0) return m; else return gcd(n,m % n); } |
|
//非递归实现 int gcd2(int m,int n) { if (m < n) { int tmp = m; m = n; n = tmp; } if (n == 0) return m;
while (n > 0) { int tmp = m % n; m = n; n = tmp; } return m; } |
这里给出了最大公约数的算法，那怎么求最大公倍数呢？其实知道了最大公约数，最小公倍数的求法就简单了：
int gbs(int m,int n)
{
return m*n/gcd(m,n);
}