int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); }
欧几里得算法使计算两个数的最大公约数的传统算法，无论从理论还是效率上都是很好的算法。然而，当所给定的整数超出了计算机的表示能力，则计算过程就需要由用户来专门设计。1961年J.Stein提出了Stein算法解决了上述问题。它只有整数的移位和加减两种运算。
int Stein(int a,int b){ if(a==0) return b; if(b==0) return a; if(a%2==0&&b%2==0) //a,b都是偶数 return 2*Stein(a>>1,b>>1); else if(a%2==0) //只有a是偶数 return Stein(a>>1,b); else if(b%2==0) //只有b是偶数 return Stein(a,b>>1); else //a,b都不是偶数 return Stein(abs(a-b),min(a,b)); }
原文：http://www.cnblogs.com/wintersong/p/4369164.html
