求最大公约数以及最小公倍数

最大公约数(greatest common divisor因子, GCD)。

最小公倍数(least common multiple倍数, LCM)。

1.群举法

首先给出两个数a和b，从两数较小的数开始，找到满足a和b同时可以被其整除的最大的约数。

#include <stdio.h>
int gcd(int a, int a)
{
	int temp = 0;
	temp = (a<b) ? a : b;
	while (temp > 0)
	{
		if ((a%temp == 0) && (b%temp == 0))
			break;
		--temp;
	}
	return temp;
}
           

2.辗转相除法

首先简单介绍一下辗转相除法： 辗转相除法又名欧几里得算法，是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。最后的余数为0时的除数就是这两个数的最大公约数。

非递归版本：

#include <stdio.h>
//不用判断两个数的大小关系，因为小数除大数
//第一次除完就转换为大数除小数了
int gcd(int a, int b)
{
	while (b > 0)
	{
		int rem = a % b;
		a = b;
		b = rem;
	}
	return a;
}
           

递归版本：

int gcd(int a, int b) //求两个数的最大公约数
{
	if ((a%b) == 0)
		return b;
	else
		return GCD(b, a%b);
}
           

3.更相减损法

int gcd(int a, int b)
{
	while (a != b)
	{
		if (a > b)
			a -= b;
		else
			b -= a;
	}
	return a;
}
           

测试代码：

#include <stdio.h>
int main()
{
	int a = 9, b = 21;
	int temp = gcd(a, b);
	printf("%d\n", temp);
	return 0;
}
           

求最小公倍数：

因为两个数的最大公约数和最小公倍数有如下关系：

最大公约数 x 最小公倍数 = 两数的乘积
           

所以可以用最大公约数直接求最小公倍数。

int lcm(int a, int b)  //求两个数的最小公倍数
{
	return a*b/gcd(a, b);
}
           

穷举法求两数的最小公倍数：

#include <stdio.h>
int lcm(int a, int b)
{
	int temp = 0;
	if (a < b)
	{
		a = a + b;
		b = a - b;
		a = a - b;
	}
	temp = a;
	while (temp % b != 0)
		temp += a;
	return  temp;
}
int main()
{
	int a = 3, b = 5;
	int temp = lcm(a, b);
	printf("%d\n", temp);
	return 0;
}