**

辗转相除法

**

#include<iostream>
using namespace std;
int main()
{	
	int a,b,temp,r,p;
	cout<<"请输入两个数:"<<endl;
	cin>>a>>b;
	p=a*b;
	if(a<b)
	{
		temp=a;
		a=b;
		b=temp;       //按从大到小的顺序排列
	}
	while(b!=0)
	{
		r=a%b;
		a=b;                              / /循环求余数
		b=r;
	}
	cout<<"最大公约数为:"<<a<<endl;  //a就是上一步的余数。上一步的余数就是b，也就是上一步的r。
	cout<<"最小公倍数为:"<<p/a<<endl;
	return 0;
}

用（a，b）表示a和b的最大公约数。
例如，求（319，377）：
∵ 377÷319=1（余58）
∴（377，319）=（319，58）；
∵ 319÷58=5（余29），
∴ （319，58）=（58，29）；
∵ 58÷29=2（余0），
∴ （58，29）= 29；
∴ （319，377）=29.
也就是说，求两个数的最大公约数时，先用较大数除以较小数，如果能整除，最大公约数就等于较小数；否则用较小数除以第一步的余数，如果能整除，最大公约数就等于第一步的余数；否则，用当前获得的余数除以上一步的余数，直到能整除为止。此时作为除数（就是上一步的余数）的那个数就是最开始那两个数的最大公约数。