计算最大公约数的几种算法【网络整理】

=============================================================

来自百度文库：http://wenku.baidu.com/link?url=yRVykgoauSWZnZv5j17zH4tBWJeU7s5teXzl56OPHYP0FNJZ3AEaVJZ5bjK6qKRynfX5R2P0azdNhZIGytPmAcNjP4ZkcOnXCtcK28ce97S

=============================================================

.

1、查找约数法．
先分别找出每个数的所有约数，再从两个数的约数中找出公有的约数，其中最大的一个就是最大公约数．

例如，求12和30的最大公约数．
12的约数有：1、2、3、4、6、12；
30的约数有：1、2、3、5、6、10、15、30．
12和30的公约数有：1、2、3、6，其中6就是12和30的最大公约数．

2  更相减损术

《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

　　翻译成现代语言如下：

　　第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

　　第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

　　则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

　　其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。

　　3、辗转相除法．

　　当两个数都较大时，采用辗转相除法比较方便．其方法是：

　　以小数除大数，如果能整除，那么小数就是所求的最大公约数．否则就用余数来除刚才的除数；再用这新除法的余数去除刚才的余数．依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数．

　　例如：求4453和5767的最大公约数时，可作如下除法．

　　5767÷4453＝1余1314

　　4453÷1314＝3余511

　　1314÷511＝2余292

　　511÷292＝1余219

　　292÷219＝1余73

　　219÷73＝3

　　于是得知，5767和4453的最大公约数是73．

　　辗转相除法适用比较广，比短除法要好得多，它能保证求出任意两个数的最大公约数．

4、求差判定法．

　　如果两个数相差不大，可以用大数减去小数，所得的差与小数的最大公约数就是原来两个数的最大公约数．例如：求78和60的最大公约数．78－60＝18，18和60的最大公约数是6，所以78和60的最大公约数是6．

　　
如果两个数相差较大，可以用大数减去小数的若干倍，一直减到差比小数小为止，差和小数的最大公约数就是原来两数的最大公约数．例如：求92和16的最大公约数．92－16＝76，76－16＝60，60－16＝44，44－16＝28，28－16＝12，12和16的最大公约数是4，所以92和16的最大公约数就是4．

　　5、分解因式法．

　　先分别把两个数分解质因数，再找出它们全部公有的质因数，然后把这些公有质因数相乘，得到的积就是这两个数的最大公约数．

　　例如：求125和300的最大公约数．因为125＝5×5×5，300＝2×2×3×5×5，所以125和300的最大公约数是5×5＝25．

　　6、短除法．

　　为了简便，将两个数的分解过程用同一个短除法来表示，那么最大公约数就是所有除数的乘积．

　　例如：求180和324的最大公约数．

　　因为：

5和9互质，所以180和324的最大公约数是4×9＝36．

　　7、除法法．

　　当两个数中较小的数是质数时，可采用除法求解．即用较大的数除以较小的数，如果能够整除，则较小的数是这两个数的最大公约数．

　　例如：求19和152，13和273的最大公约数．因为152÷19＝8，273÷13＝21．（19和13都是质数．）所以19和152的最大公约数是19，13和273的最大公约数是13．

　　8、缩倍法．

　　如果两个数没有之间没有倍数关系，可以把较小的数依次除以2、3、4……直到求得的商是较大数的约数为止，这时的商就是两个数的最大公约数．例如：求30和24的最大公约数．24÷4＝6，6是30的约数，所以30和24的最大公约数是6．

 ========================================================================

博客园No Joking：http://www.cnblogs.com/visayafan/archive/2011/08/11/2135345.html

=========================================================================

a = b × r_1 + q_1
if q_1 = 0
      then return b
else
b = q_1 × r_2 + q_2
if q_2 = 0
      then return q_1
else

int gcd(int a, int b)
{
        if(!b) return a;
        else  return gcd(b, a%b );
}

int gcd(int a, int b)
{
        int c = a%b;
        while(c){
                a = b;
                b = c;
                c = a % b;
        }
        return b;
}

欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理： 
定理：gcd(a,b) = gcd(b,a mod b)

其算法用C++语言描述为：
int gcd(int m, int n)
{
 if (m == 0)
  return n;
 if (n == 0)
  return m;
 if (m < n)
 {
  int tmp = m;
  m = n;
  n = tmp;
 }
 while (n != 0)
 {
  int tmp = m % n;
  m = n;
  n = tmp;
 }

 return m;
}

Stein算法(以下理论请参考http://blog.vckbase.com/arong/archive/2004/06/15/458.html），代码是我加上的。

欧几里德算法是计算两个数最大公约数的传统算法，他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。
考虑现在的硬件平台，一般整数最多也就是64位，对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。

Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法 算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。

为了说明Stein算法的正确性，首先必须注意到以下结论：

gcd(a,a) = a，也就是一个数和他自身的公约数是其自身 
gcd(ka,kb) = k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数必然能被2整除 
有了上述规律就可以给出Stein算法如下：

1.如果A=0，B是最大公约数，算法结束 
2.如果B=0，A是最大公约数，算法结束 
3.设置A1 = A、B1=B和C1 = 1 
4.如果An和Bn都是偶数，则An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可) 
5.如果An是偶数，Bn不是偶数，则An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (很显然啦，2不是奇数的约数) 
6.如果Bn是偶数，An不是偶数，则Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (很显然啦，2不是奇数的约数) 
7.如果An和Bn都不是偶数，则An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn 
8.n++，转4 
这个算法的原理很显然，所以就不再证明了。现在考察一下该算法和欧几里德方法效率上的差别。

考虑欧几里德算法，最恶劣的情况是，每次迭代a = 2b -1,这样，迭代后，r= b-1。如果a小于2N，这样大约需要 4N次迭代。而考虑Stein算法，每次迭代后，显然AN+1BN+1≤ ANBN/2，最大迭代次数也不超过4N次。也就是说，迭代次数几乎是相等的。但是，需要注意的是，对于大素数，试商法将使每次迭代都更复杂，因此对于大素数Stein将更有优势。

其算法用C++语言描述为：
bool is_even(int n) 
{
 return !(n & 1);
}
int gcd2(int m, int n)
{
 int c = 1;
 while (m != 0 && n != 0)
 {
  if (is_even(m) && is_even(n))
  {
   m >>= 1;
   n >>= 1;
   c <<= 1;
  }
  else if (is_even(m) && !is_even(n))
  {
   m >>= 1;
  }
  else if (!is_even(m) && is_even(n))
  {
   n >>= 1;
  }
  else if (!is_even(m) && !is_even(n))
  {
   int m1 = m;
   int n1 = n;
   m = abs(m-n);  //crt库函数
   n = min(m1, n1);//crt宏
  }
 }

 return c * n;
}