[编程入门]最大公约数与最小公倍数（C语言题解）

解题思路:

很多人使用辗转相除法来获得GCD和LCM，但在中学大家更多的应该是使用老师讲的短除法，所以这个代码采用了短除法的思路。

参考代码:

#include<stdio.h>
int main()
{
	int m , n; 
	int a, b , i , j;
	int GCD , LCM;
	scanf("%d %d", &m, &n);
	a = m>n? m:n;  //a存储较大的数 
	b = m>n? n:m;  //b存储较小的数 
	for(i = b; i>= 1 ; i--)  //最大公约数小于等于较小的数 
	{
		if( a%i==0&&b%i==0 )
		{
			GCD = i;
			printf("%d\n", GCD); break;
		}
	}
	for(j = a; j<= a*b ; j++)  //最小公倍数大于等于较大的数 
	{
		if( j%a==0&&j%b==0 )
		{
			LCM = j;
			printf("%d\n", LCM); break;
		}
	}
	return 0;
}

注意事项:

第10行的i为什么从b到1，因为最大公约数小于等于较小的数而又接近这个较小的数，比如4和8（GCD=4），6和8（GCD=2），然后两个数都能被最大公约数整除，所以两个数对i取余都等于0时，i=GCD，所以把i从1到b倒序遍历能更快找到GCD；同理第18行的j从a到ab，最小公倍数大于等于较大的数，小于等于两个数的乘积，比如4和8（LCM=8），6和7（LCM=42），所以把j从a到ab顺序遍历，然后最小公倍数都能被两个数整除，所以j对两个数取余都等于0时，j=LCM。