汗~學過又忘掉的東西。。。那就記錄下來，讓忘卻來得更猛烈些吧！

//遞歸實現

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);

}
?

求最大公約數的stein算法(zz)
astrophor 發表于 2006-9-9 20:24:00

在處理大數時比較有效，因為沒有用到大數的除法運算，速度會很快。

int gcd(int a,int b)
{
if (a == 0) return b;
if (b == 0) return a;
if (a % 2 == 0 && b % 2 == 0) return 2 * gcd(a/2,b/2);
else if (a % 2 == 0) return gcd(a/2,b);
else if (b % 2 == 0) return gcd(a,b/2);
else return gcd(abs(a-b),min(a,b));
}