转载：https://www.cnblogs.com/hexiaochun/archive/2012/09/03/2668250.html

 

今天研究了一下最大公约数的求法，在网上也找了不同的解法，现在就想总结一下，拿出来分享给大家，共同 学习

首先讲一个什么是公约数，这个问题我们小学都学过，可能有一部分人已经忘记了，所以还是讲一下，假设有两个数a,b,所谓的公约数就是能把a,b整除的最大整数。

明白了要求我们就来解决问题，一拿到问题我们都应该都能想到一个方法，就是使用穷举法，从2开始一个个找，到一个两个都能除的就记录起来，一直找到小于min(a,b)结束，

记录到的值就是他们的最大公约数代码由下：

代码片段，双击复制

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22

//找出最大公约数,穷举法         public  static  int  getMaxDivide_ab( int  a, int  b){                 int  value= 1 ;                 int  max;                 int  min;                 if (a==b){                         return  a;                 }                 if (a>b){                         max=a;                         min=b;                 } else {                         max=b;                         min=a;                 }                 for ( int  i= 2 ;i<min;i++){                         if ( 0 ==max%i && 0 ==min%i){                                 value=i;                         }                 }                 return  value;         }

第二种方法是使用欧几里德算法，这个已经有2000+年的历史了，这个比起上一个来的要高效，假设我们的最大公约数表示为f(a,b),并且有a>=b>0,

欧几里德就给了我们一个很好的定理，f(a,b)=f(b,a%b),有了这个等式我们就很容易得出这个算法的递归式，现在我们来看下这个等式是怎么来的

设有 r=a/b ,q=a%b  

所以就有 a=a/b*b+q  ----(这里的a/b*b!=a   ，原因就是我们用的是整数来计算的)

也就是a=r*b+q     变换一下有：q=a-r*b      设d=f(a,b)，a/d=m,b/d=n;则  有q=dm-r*dn=d(m-rn)

所以q/d也为0；设d|q表示d是q的约数；以下相同；

又有d|b;所以有d|(b,q),设D是(b,q)的最大公约数，则会有d<=D=f(b,q);

再回到前面r=a/b,q=a%b这两个条件有

a=r*b+q,由于D|(b,q),所以D|a,所以有D|(a,b)

所以有D<=d=f(a,b),结合上部分就有d<=D <+d,及D=d;

所以得证；

代码实现由下：

代码片段，双击复制

01 02 03 04 05 06 07 08 09 10 11 12

public  static  int  oujilide( int  a, int  b){                 if (a<b){                         int  temp;                         temp=a;                         a=b;                         b=temp;                 }                 if ( 0 ==b){                         return  a;                 }                 return  oujilide(b,a%b);         }