最大公约数常用两种方法及代码集锦

 

1、欧几里得方法（euclid）

     思想：gcd(a,b)=gcd(b,r)  r = a % b;

     欧几里得算法即是要证明gcd(a,b)=gcd(b,r)。证明：

     1.令c=gcd(a,b),则有a=mc,b=nc。因为r=a mod b,固有r=a-kb=mc-knc=(m-kn)c,所以m-kn和c为r的因数。     

     2.m-kn与n互质，【否则，可设m-kn=xd，n=yd，（d>1），则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数成为cd，而非c】

     3.gcd=(b,r)=c=gcd(a,b)。

     

int Euclid(int a,int b){
    while(a=a%b){
        a=a+b;
        b=a-b;
        a=a-b;
    }
    return b;
}

 递归：

int euclid(int x, int y)
｛
    if (x < y) x <-> y;
    if (y) return euclid(y, x%y);
    else return x;
｝

      迭代：

int euclid(int x, int y)
{
    while(a = a % b)
    {
        a ^=b;
        b ^= a;
        a ^= b;
     }
     return b;
}

     迭代与递归的区别：一个函数进行自身某种法则的复合是迭代；迭代和递归都是用循环结构

     对于迭代，其实解决问题的方法是不断的修改迭代变量的值，直到碰到令循环失败的迭代变量；递归则是，不断产生原始问题的简化副本，直到问题简单到基本情况。递归使用重复调用函数的机制，不断为程序申请栈空间以存放函数数据，使算法的时间和空间复杂度很大，而迭代则是在循环体内部进行的，就避免了使用递归带来的问题。从理论上来讲，能使用递归解决的问题，就能使用迭代来解决。

2、二进制最大公约数算法

     思想： a、b 均为偶数， gcd(a,b) = 2 * gcd(a/2, b/2)

               a为偶数，b为奇数， gcd(a,b) = gcd(a/2 , b)

               a为奇数，b为偶数，gcd(a,b) = gcd(a, b/2)

               a、b均为奇数， gcd(a,b) = gcd((a-b)/2, b)

     经典c代码实现一：

int gcd(int a,int b){
    int c=1;
    while(a-b){
        if(a&1){
            if(b&1){
                if(a>b)a=(a-b)>>1;
                else b=(b-a)>>1;
             }
             else b>>=1;
         }
         else{
             if(b&1)a>>=1;
             else
             {
                 c<<=1,a>>=1,b>>=1;
             }
       }
    }
    return c*a;
}

     经典c代码实现二

          

int gcd(int u,int v){
    int k=1,t;
    while(~u&1 && ~v&1){
       k<<=1,u>>=1,v>>=1;
    }
    t=(u&1)?-v:u>>1;
    do{
       while(~t&1)t>>=1;
       if(t>0)u=t;else v=-t;
    }while(t=u-v);
    return u*k;
}

     经典C代码实现三

     

int gcd(int x,int y)
{
     int i,j,t;
     if(x==0) return y;
     if(y==0) return x;
     for(i=0; 0==(x & 1); x>>=1,++i);
     for(j=0; 0==(y & 1); y>>=1,++j);
     if (j < i) i = j;
     while(1)
     {
          if (x < y) t = y,y = x,x = t;
          if (0 == (x -= y)) return y << i;
          for (; 0 == (x & 1 );x >>= 1 );
     }
}

博文中代码的实现是参考的现有网上的朋友贡献的，链接地址忘了，感谢你们。