编程之美----最大公约数问题

求两个很大的数的最大公约数问题。

解法一：辗转相除法，但当数很大时，取模运算很耗时间。

解法二：利用f(x,y) = f(x-y, y)可以避免取模，但是当第一个数很大，而第二个数很小如1时，也比较耗时。

解法三：对于y和x来说，如果y=k*y1, x= k*x1,那么f(y,x)=k*f(y1,x1)。如果x=p*x1,假设p是素数，并且y%p!=0,那么f(x,y)=f(p*x1,y)=f(x1,y)。于是对于二进制表示的大整数而言可以每次除二了。

 1 BigInt gcd(BigInt x, bigInt y)
 2 {
 3      if(x<y)  
 4             return gcd(y,x);
 5     if(y==0)
 6             return x;
 7     else 
 8     {
 9          if(IsEven(x))
10         {
11             if(IsEven(y))
12                 return (gcd(x>>1,y>>1)<<1);
13             else 
14                 return gcd(x>>1,y);
15         }
16         else 
17         {
18             if(IsEven(y))
19                 return gcd(x,y>>1);
20             else 
21                 return gcd(y,x-y);
22         }
23     }
24 }

View Code