C语言算法--最大公约数
基本算法——辗转相除法
问题:输出两个正整数a,b, 且0
p 从a 开始,检测p 是否能同时整除a 和b, 是则停止循环,不是则令p 减1,继续检测。
q 从b 开始,检测q 是否能同时被a 和b 整除,是则停止循环,不是则令续检测。 源程序1
#include void main() {
int a,b, p, q; do{
printf("请输入a 和b:\n"); scanf("%d%d",&a,&b); } while ( ab); p=a;
while( a%p!=0 || b%p!=0) p--;
printf("这两个数的最大公约数是%d\n",p); q=b;
while( q%a!=0 || q%b!=0) q++;
printf("这两个数的最小公倍数是%d\n",q); }
q 增1,继
改进——已知整数a,b 及其最大公约数p, 则直接可推算出最小公倍数q :
q= a*b/p;
源程序2
#include void main() {
int a,b, p, q; do{
printf("请输入a 和b:\n"); scanf("%d%d",&a,&b); } while ( ab); p=a;
while( a%p!=0 || b%p!=0) p--;
printf("这两个数的最大公约数是%d\n",p);
q= a*b/p;
printf("这两个数的最小公倍数是%d\n",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为被除数,以余数381为除数, 相除得: 商为2,余数为254 以除数381为被除数, 以余数254为除数, 相除得: 商为1 ,余数为127 以除数254为被除数, 以余数127为除数,
相除得: 商为2,余数为0
~~发现能整除,则127就是最大公约数。整个计算过程为:
数学证明: b=as+r (0≤r ≤b-1),且a,b 的最大公约数用符号(a,b )代表 若r=0,显然(a,b )=a;
若r≠0, 由于b=as+r,每个能整除a,r 的整数都能整除b →能同时整除a,b, 故有
(a,r) | (a,b)
另一方面,r=b-aq, 每个能整除a,b 的整数都能整除r →能同时整除a,r, 故有
(a,b) | (a,r)
因此(a,b )=(a,r)
辗转相除法源程序:
#include void main() {
int a,b,r, m; do{
printf("请输入a 和b:\n"); scanf("%d%d",&a,&b); }while( ab); m=a*b;
do{ r=b%a;
b=a; a=r; }while(r!=0);
printf("这两个数的最大公约数是%d\n",r );
printf("这两个数的最小公倍数是%d\n", m/r); }
//不能写“a*b/r”