最大公因数最小公倍数（辗转相除法）_用辗转法求最大公因数和最小公倍数的计算题

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公约数为1
当余数为0时最大公因数为此时的除数1
最小公倍数为 （1997*615）/1

#include<stdio.h>
int main()
{
	int m,n;
	scanf("%d%d",&m,&n);//输入两个值
	int s=m*n;//得乘积为计算最小公倍数
	int temp;
	if(n>m)
	{
		temp=n;
		n=m;
		m=temp;
	}
	while(m%n!=0)//辗转相除法
	{
		temp=n;//n为除数
		n=m%n;//上次计算的余数为下次的除数
		m=temp;//上次的出数为下次的被除数
	}
	printf("最大公因数%d",n);
	printf("最小公倍数%d",s/n);//由规律得（原来两个数的乘积）/（最大公因数）=最小公倍数
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23