求最大公约数的原理及算法实现

《求最大公约数的原理及算法实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.辗转相除法GCD算法的基本原理  DCD-GreatestCommonDivisor欧几里得定理：   若a=b*r+q，则GCD(a,b)=GCD(b,q)。证明：  假设c=GCD(a,b)   则存在m使得 a=m*c,b=n*c;  因为a=b*r+q,  则 q=a-b*r=m*c-n*c*r=(m-n*r)*c;   因为b=n*c,q=(m-n*r)*c  故要证明GCD(a,b)=GCD(b,q)，即证明n与m-n*r互质   下面证明m-n×r与n互质：   假设不互质，则存在公约数k使得m-n*r=x*k,n

2、=y*k.   则:   a =m*c=(n*r+x*k)*c=(y*k*r+x*k)*c=(y*r+x)*k*c    b=n*c=y*c*k  则GCD(a,b)=k*c,与c=gcd(a,b)矛盾2.辗转相除法算法的实现2.1递归实现intGCD(inta,intb){    if(!b)         returna;     else         returnGCD(b,a%b); }自己改进intGCD(inta,intb){     if(!(a%b))         returnb;     else    

3、     returnGCD(b,a%b); }2.2迭代实现intGCD(inta,intb){intc=a%b;while(c)        {                a=b;b=c;c=a%b;}returnb;} 3.更相减损法更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。      《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等

4、数约之。”翻译成现代语言如下：第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减去小数。继续这个操作，直到所得的减数和差相等为止。则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。例如：用更相减损术求260和104的最大公约数。解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26

5、。此时65是奇数而26不是奇数，故把65和26辗转相减：65-26=3939-26=1326-13=13所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即13*2*2=52。2.更相减损法算法的实现2.1递归实现#include intmain(void){  intnum=0,result,a,b;  scanf("%d%d",&a,&b);   while(!(a%2)&&!(b%2))   {     num++;     a/=2;     b/=2;  }   result=pow(2,

6、num)*GCD(a,b);  printf("GCD:%d",result);  return0;} intGCD(inta,intb){  if(a>b)  {     if((a-b)==b)        returnb;     else        returnGCD(b,a-b);   }  else  {     if((b-a)==a)        returna;     else        returnGCD(a,b-a);   }}2.2迭代实现#includeintmain(v

7、oid){  intnum=0,result,a,b;  scanf("%d%d",&a,&b);  while(!(a%2)&&!(b%2))   {     num++;     a/=2;     b/=2;  }   result=pow(2,num)*GCD(a,b);  printf("GCD:%d",result);  return0;}intGCD(inta,intb){  if(a

8、if((a-b)>b)         a=a-b;     else     {        a=b;        b=a-b;      }   }returnb;} 3.辗转相除法与更相减损术的区别（1）都是求最大公因数的方