基本算法——辗转相除法
问题：输出两个正整数a,b,且0<a<b, 输出其最大公约数p和最小公倍数q
解法1——
p从a开始，检测p是否能同时整除a和b, 是则停止循环，不是则令p减1，继续检测。

q从b开始，检测q是否能同时被a和b整除，是则停止循环，不是则令q增1，继续检测。

源程序1
#include <stdio.h>
void main()
{
int a,b, p, q;
do{
printf("请输入a和b:\n"); scanf("%d%d",&a,&b);
} while ( a<0 || b<0 || a>b);
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);
}
改进——已知整数a,b及其最大公约数p,则直接可推算出最小公倍数q：
q= a*b/p;
源程序2
#include <stdio.h>
void main()
{
int a,b, p, q;
do{
printf("请输入a和b:\n"); scanf("%d%d",&a,&b);
} while ( a<0 || b<0 || a>b);
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 <stdio.h>
void main()
{
int a,b,r, m;
do{
printf("请输入a和b:\n");
scanf("%d%d",&a,&b);
}while( a<0 || b<0 ||a>b);
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”}。