C语言每日一练——Day02：求最小公倍数(3种方法)

一、什么是公倍数?

📖通过直观的理解，我们很容易知道，所谓的公倍数就是两个数共有的倍数；那么最小公倍数，就是他们共有的倍数中最小的那个数。比如2和4的最小公倍数是4,15和20的最小公倍数是60……

二、求解两个数的最小公倍数

🍑1、枚举法

思路： 已知两个数的最小公倍数大于等于两个数的最大值，所以可以先求出两个数的较大值max，用max分别试除两个数，如果能整除，max即为两个数的最小公倍数；不能整除，让max=max+1直到找到最小公倍数为止。

✍️如：求12和8的最小公倍数

1. 先求较大值12，12不是两个数的最小公倍数
2. 12+1=13,13+1=14……，23+1=24可以整除这两个数
3. 所以24是最小公倍数

📝代码展示：

//枚举法
#include
int main()
{
	int x = 0;
	int y = 0;
	scanf("%d %d",&x,&y);
	int max = (x > y ? x : y);//取最大值
	while (max%x != 0 || max%y!= 0)//如果不能同时整除
	{
		max++;//每次增加1
	}
	printf("%d",max);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

🍑2、公式法

思路： 两个数的最小公倍数数等于两个数的乘积除以两个数的最大公约数。即：x，y的最小公倍数 min(公倍数)=x*y÷max(公约数)

✍️如：求12和8的最小公倍数

1. 求得12和8的最大公约数是4
2. 即12和8的最小公倍数是12×8÷4=24

📝代码展示：

//公式法：
#include
int main()
{
	int x = 0; 
	int y = 0;
	scanf("%d %d",&x,&y);
	int z = x * y;//将两个数的乘积存起来方便后续使用
	    //求最大公约数
	while (x % y != 0)
	{
		int tmp = x % y;
		x = y;
		y = tmp;
	}
	int min = z / y;//最小公倍数
	printf("%d",min);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

🍑3、迭乘法

思路： 已知两个数的公倍数一定与这两个数存在倍数关系，那么求解最小公倍数我们就可以将其中一个数依次扩大1倍、2倍、3倍……直到出现第一个扩大n倍的数可以同时整除这两个数，这个数就是最小公倍数。

✍️如：求12和8的最小公倍数

1. 12×1=12,12不是8的倍数
2. 12×2=24,24是8的倍数
3. 24是12和8的最小公倍数

📝代码展示：

//迭乘法
#include
int main()
{
	int x = 0;
	int y = 0;
	scanf("%d %d",&x,&y);
	int i = 1;
	while (x * i %y != 0)
	{
		i++;
	}
	printf("%d",x*i);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

📖总结

上述三种方法中：

• 迭乘法效率最高，建议使用。
• 枚举法效率最低，不推荐使用。