[算法贴]如何最快地算出两个数的最大公约数？

Question

最简单的
public static int gxd(int m, int n)
    {
        int gxd = 1;int result = 0;
        for (; gxd <= m && gxd <= n;gxd++ )
        {
            if (m % gxd == 0 && n % gxd == 0)
                result = gxd;
        }
        return result;
    }
可惜效率不怎么的！

Answer 1

经典的欧几里德算法//递归实现
int zuidagongyue(int m,int n)
{
       if (m < n)
       {
              int tmp = m;
              m = n;
              n = tmp;
       }
       if (n == 0)
              return m;
       else
              return zuidagongyue(n,m % n);
} 
//非递归实现
int zuidagongyue2(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;
}
 

Answer 2

        static int GCD(int a, int b)
        {
            int gcd;
            if (a < b)
                gcd = GCD(b, a);
            else
            {
                while (b != 0)
                {
                    int t = a % b;
                    a = b;
                    b = t;
                }
                gcd = a;
            }
            return gcd;
        } 

Answer 3

精简一下：        static int GCD(int a, int b)
        {
            if (a < b)
                return GCD(b, a);
            else if (a == b)
                return a;
            while (b != 0)
            {
                int t = a % b;
                a = b;
                b = t;
            }
            return a;
        }

Answer 4

应该把数据类型改改，以接受更大数值的参数：        static ulong GCD(ulong a, ulong b)
        {
            if (a < b)
                return GCD(b, a);
            else if (a == b)
                return a;
            while (b != 0)
            {
                ulong t = a % b;
                a = b;
                b = t;
            }
            return a;
        }

Answer 5

#include <stdio.h>
//主体
int rr(int m,int n)
{
while(m&&n) m>n?m=m%n:n=n%m;
return m=m>n?m:n;
}
int main()
{
    int m,n;
while(scanf("%d%d",&m,&n)==2)
    printf("%d\n",rr(m,n));
return 0;
}