[算法]求最大公约数：二进制欧几里德算法(Binary Euclid's Algorithm)

BEINGJESSE

辗转相除，正确

woolzey

递归的辗转相除精炼归精炼，效率可就低死了。除法这种东西可是大害。

特别是当两个数非常大的时候，只有加减和移位的二进制欧几里德算法的速度会非常好。

Heefan

be useful in Crypthography...but fix the type of integer first

lax

1. 
   
2. 
   
3. int gcd(int a, int b) //最大公约数
   
4. {
   
5. while(a && b && a!=b)
   
6. { a>b ? a = a%b : b = b % a; }
   
7. return a;
   
8. }
   
9. 
   

复制代码

http://www.liulantao.com/blogs/lltaichi/2007/11/c_06.html

yuhch123

...ls的有bug,a=4,b=2算出来是0吧