c语言算法——最大公约数

《c语言算法——最大公约数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基本算法——辗转相除法问题：输出两个正整数a,b,且0voidmain(){inta,b,p,q;do{printf("请输入a和b:");scanf("%d%d",&a,&b);}while(a<0

2、

3、b<0

4、

5、a>b);p=a;while(a%p!=0

6、

7、b%p!=0)p--;pr

8、intf("这两个数的最大公约数是%d",p);q=b;while(q%a!=0

9、

10、q%b!=0)q++;printf("这两个数的最小公倍数是%d",q);}改进——已知整数a,b及其最大公约数p,则直接可推算出最小公倍数q：q=a*b/p;源程序2#includevoidmain(){inta,b,p,q;do{printf("请输入a和b:");scanf("%d%d",&a,&b);}while(a<0

11、

12、b<0

13、

14、a>b);p=a;while(a%p!=0

15、

16、b%p!=0)p--;printf("这两

17、个数的最大公约数是%d",p);q=a*b/p;printf("这两个数的最小公倍数是%d",q);}解法1的缺点：效率低。例如a=1397,b=2413,其最大公约数p=127，为得到p，共循环了1397-127+1=1171次。如何提高效率？解法2——辗转相除法，在西方称为Euclid(欧几里德)算法。以计算（1397，2413）的最大公约数为例：以大数2413为被除数，以小数1397为除数，相除得：商为1，余数为1016以除数1397为被除数，以余数1016为除数，相除得：商为1，余数为381以除数1016为被除数，以余数38

18、1为除数，相除得：商为2，余数为254以除数381为被除数，以余数254为除数，相除得：商为1，余数为127以除数254为被除数，以余数127为除数，相除得：商为2，余数为0～～发现能整除，则127就是最大公约数。整个计算过程为：被除数b除数a商s余数r241313971101613971016138110613812254381254112725412720数学证明：b=as+r（0≤r≤b-1），且a,b的最大公约数用符号（a,b）代表若r=0，显然（a,b）=a;若r≠0,由于b=as+r，每个能整除a,r的整数都能整除bà能同时整除

19、a,b,故有(a,r)

20、(a,b)另一方面，r=b-aq，每个能整除a,b的整数都能整除rà能同时整除a,r,故有(a,b)

21、(a,r)因此（a,b）=(a,r)辗转相除法源程序:#includevoidmain(){inta,b,r,m;do{printf("请输入a和b:");scanf("%d%d",&a,&b);}while(a<0

22、

23、b<0

24、

25、a>b);m=a*b;do{r=b%a;b=a;a=r;}while(r!=0);printf("这两个数的最大公约数是%d",r);printf("这两个数的最小

26、公倍数是%d",m/r);//不能写“a*b/r”}