汗~学过又忘掉的东西。。。那就记录下来，让忘却来得更猛烈些吧！

//递归实现

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