多种方法求两个正整数的最大公约数和最小公倍数

鲁迅说过：“求解最大公约数和最小公倍数有很多方法”，公约数，就是几个数共有的约数，最大公约数，就是公约数中最大的那个数，公倍数，就是几个数共有的倍数，最小公倍数，就是公倍数中最小的那个数。虽然看起来是句废话，其实它就是废话……下面我们看一下求解最大公约数和最小公倍数的几种方法。

求任意两个正整数的最大公约数

最大公约数（Greatest Common Divisor，GCD），先说约数，a能被b整除，b就是a的约数，几个数共有的约数就是这几个数的公约数，公约数中最大的那个数就是最大公约数。举个例子，4和20的公约数有1，2，4，最大公约数是4。可见两个数的最大公约数必不大于两数中最小的那个。

思路一：如果求出最大公约数，穷举法从小到大（从1到两数中较小的一个）遍历，然后输出最大的那个，这样做比较麻烦，不妨我们从大到小（从两数中较小的一个到1）遍历，第一个能同时整除两个数的那个即为所求。

int main()
{
	int a = 0;
	int b = 0;
	int tmp = 0;
	int i = 0;
	scanf("%d %d", &a, &b);
	//a中存储较大的那个数，b存储小数，当a<b时交换两数
	if (a < b) {
		tmp = a;
		a = b;
		b = tmp;
	}
	//从b到1遍历，找最大公约数
	for (i = b; i > 1; i--) {
		//同时整除两个数的那个数即为所求，找到后break结束遍历
		if (a % i == 0 && b % i == 0) {
			break;
		}
	}
	printf("%d", i);
	return 0;
	
}

思路二：我们可以用辗转相除法求最大公约数，例如15和20两个数，15%20=15，20%15=5，15%5=0，两数相除，将除数当作下个算式的被除数，余数当作除数，如此往复，当余数为0时，最后一个算式的除数5就是15和20的最大公约数。我可能说的有些复杂了，看代码就懂了，还有这一思路的妙处是不用判断两数的大小。

int main()
{
	int a = 0;
	int b = 0;
	int c = b;
	scanf("%d %d", &a, &b);
    //辗转相除，余数为0跳出循环
	while (a % b != 0) {
		c = a % b;
		a = b;
		b = c;
	}
	printf("%d", b);

}

求任意两个正整数的最小公倍数

最小公倍数（Least Common Multiple，LCM），若a能被b整除，a就是b的倍数，对于两个整数来说，两数共有倍数中最小的一个便是最小公倍数。

思路一：我们可以借助最大公约数求最小公倍数。两数乘积除以最大公约数便是最小公倍数。若a和b的最大公约数是c，那么最小公倍数便是a*b/c，最大公约数的求法如上，这一思路这里不再列出代码。

思路二：两个数的最小公倍数就是能被两数整除的那个最小的数（废话文学），如果较大的数能被较小的数整除，那么较大的数就是两数的最小公倍数，否则要从较大的数开始，一次向上遍历，知道找出能同时被两数整除的那个数。举个例子，5和25，25能被5整除，25就是5和25的最小公倍数；5和7，较大的数7不能被5整除，7一直加1，变成8，9，10……，35，知道35，35能被5和7整除，35便是5和7的最小公倍数。废话有点多了，上代码。

int main()
{
	int a = 0;
	int b = 0;
	int tmp = 0;
	int i = 0;
	scanf("%d %d", &a, &b);
	//a存放两数中较大的那个，b存放小数
	if (a < b) {
		tmp = a;
		a = b;
		b = tmp;
	}
	//从最大数开始向上计数
	for (i = a; i > 0; i++) {
		//找出最小公倍数，退出循环
		if (i % a == 0 && i % b == 0) {
			break;
		}
	}
	printf("%d", i);

}

思路三：众所周知，5和7的最小公倍数是35，35能被5和7同时整除（又是一句废话），看下面这个算式：5*i%7=0，5*i的结果既能被5整除，也能被7整除，所以5*i便是5和7的最小公倍数。

int main()
{
	int a = 0;
	int b = 0;
	int i = 1;
	scanf("%d %d", &a, &b);
	while (a * i % b) {
		i++;
	}
	printf("%d", a * i);
	return 0;
}