拿捏---＞最小公倍数-Toy模板网

这篇具有很好参考价值的文章主要介绍了拿捏---＞最小公倍数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

给定两个数，求这两个数的最小公倍数

例如：
输入：10 20
输出：20

算法思路

最小公倍数是指两个或多个整数公有的倍数中，除0以外最小的一个公倍数。

代码示例

方法一

两数乘积=最小公倍数*最大公约数

在上篇求最大公约数的四种方法中，我们已经能够求得最大公约数，借此便能求得最小公倍数

#include<stdio.h>
int main() {
	int a, b;
	scanf("%d %d", &a, &b);
	int m = a * b;
	int r = 0;
	while (r = a % b) {//r为0时，跳出循环，此时b为最大公因数
		a = b;
		b = r;
	}
	printf("%d\n", m/b);//乘积除以最大公因数等于最小公倍数
	return 0;
}

方法二

自增：循环求解

首先两个数的最小公倍数一定大于两个数中较大的那个，且小于两数之积

找出a与b之间的较大值max

利用循环，令i=max，不断++,当i能同时整除a与b时,输出i,跳出循环

即i为最小公倍数

#include <stdio.h>
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);
	int min = a > b ? a : b;//min为公倍数的可能最小取值
	while (1)
	{
		if (min % a == 0 && min % b == 0)
		{
			printf("%d", min);
			break;
		}
	}
	return 0;

方法三

两个数的最小公倍数一定是这两个数每一个的倍数，那么我们结合方法二，只需要拿出二者之一，让它成倍的增长，然后判断每增长一倍后是否整除另一个数，这样既可以减少循环的次数，还不用判断两个数的大小，是不是比方法二简单很多。文章来源地址https://www.toymoban.com/news/detail-621378.html

#include <stdio.h>
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);
	int i = 0;
	for (i = 1;; i++)
	{
		if (a * i % b == 0)
		{
			printf("%d\n", a * i);
			break;
		}
	}
	return 0;
}