求最大公约数方法的总结

一、欧几里得算法

int gcd(int a,int b){return b==0?a:gcd(b,a%b);} 

 

二、Stein算法

对于很大的数，用高精度表示，用欧几里得算法的话大数除法比较麻烦。

用这个算法会比较简单，只用到除2与加减运算。

下面的代码摘自这个网址，罪过罪过^_^

http://www.blogjava.net/renyangok/archive/2007/12/15/167956.html

 

int gcd(int a,int b){      if(a<b){  //arrange so that a>b          int temp = a;            a = b;            b=temp;      }      if(0==b)//the base case         return a;      if(a%2==0 && b%2 ==0)  //a and b are even          return 2*gcd(a/2,b/2);      if ( a%2 == 0)  // only a is even          return gcd(a/2,b);      if ( b%2==0 )  // only b is even          return gcd(a,b/2);      return gcd((a+b)/2,(a-b)/2);  // a and b are odd }

 

求多个数的最大公约数就多用几次欧几里得吧。