最小公倍数求法 (3种代码思路供参考 ) --（C语言实现）-- 详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了最小公倍数求法 (3种代码思路供参考 ) --（C语言实现）-- 详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

题目内容

正整数A和正整数B的最小公倍数是指能被A和B整除的最小的正整数值,设计一个算法，求A,B的最小公倍数

输入：

输入两个正整数A,B

输出：

输出:A,B的最小公倍数

一、题目解读

1、最小公倍数（LCM）是：能被A和B整除的最小的正整数
2、如何求最小公倍数：
思路一：
最小公倍数一定是两个数中较大的值。
加法寻找：让较大的值赋值给m，利用m可以整除A和B来判断。如果m一次可以整除A和B就找到了最小公倍数，否则就m+1看下一位数是否可以整除A和B（需要循环）;
乘法寻找：不用判断a,b谁为较大值，利用循环变量i（1-无穷），如果 a * i % b == 0或者 b * i % a== 0,就找到了最小公倍数a * i或b * i

思路二：
利用辗转相除法求出最大公约数，再（a*b）/ 最大公约数=最小公倍数

思路三：假设a,b最小公倍数为k，k/a=i,k/b=j.就有(a*i)%b==0,
利用此条件为循环条件，求出最小公倍数.

最大公约数博客

二、代码实现

1.加法寻找最小公倍数

如果找到最小公倍数就返回t，没找到就t++找下一个数是否成立。
代码如下（示例）：

//加法
int LCM(int a, int b)
{
	int t = 0;
	//将两个数中较大的给t
    //int t=a>b?a:b;三目操作符运算求两个中较大值
	if (a > b)
	{
		t = a;
	}
	else
	{
		t = b;
	}
	while (1)
	{
		if (t % a == 0 && t % b == 0)
		{
			return t;
		}
		t++;
	}
}

加法总代码

#include<stdio.h>
int LCM(int a, int b)
{
	int t = 0;
	//将两个数中较大的给t
	if (a > b)
	{
		t = a;
	}
	else
	{
		t = b;
	}
	while (1)
	{
		if (t % a == 0 && t % b == 0)
		{
			return t;
		}
		t++;
	}
}
int main()
{
	int a, b;
	scanf("%d %d", &a, &b);
	int ret=LCM(a, b);
	printf("最小公倍数=%d\n", ret);
	return 0;
}

2.乘法寻找最小公倍数

发现最小公倍数只能是两数中其中一个的整倍数，所以t是a,b中一个，t=t*i -> 如果得到的数可以整除a和b，则为最小公倍数；
代码如下（示例）：

//最小公倍数最大可能就是两数相乘
	/*for (i = 1;t<=a*b;i++)
	{
		t *= i;
		if (t % a == 0 && t % b == 0)
		{
			return t;
		}
	}*/

上述代码重复太多，很多可以省去，代码改进如下

int LCM(int a, int b)
{
	int t = 0;
	int i = 0;
	for (i = 0;; i++)
	{
		if (a * i % b == 0)
		{
			return a * i;
		}
	}
}

乘法总代码

#include<stdio.h>
int LCM(int a, int b)
{
	int t = 0;
	int i = 0;
	//最小公倍数最大可能就是两数相乘
	/*for (i = 1;t<=a*b;i++)
	{
		t *= i;
		if (t % a == 0 && t % b == 0)
		{
			return t;
		}
	}*/
	for (i = 1;; i++)
	{
		if (a * i % b == 0)
		{
			return a * i;
		}
	}
}
int main()
{
	int a, b;
	scanf("%d %d", &a, &b);
	int ret=LCM(a, b);
	printf("最小公倍数=%d\n", ret);
	return 0;
}

3、辗转相除法求解最小公倍数

辗转相除法求出最大公约数，(a*b)/最大公约数==最小公倍数

#include<stdio.h>
int GCD(int a, int b)
{
	//a%b=t
	int t = 1;
	while (t)
	{
		t = a % b;
		a = b;
		b = t;
	}
	return a;
}
int main()
{
	int a, b;
	scanf("%d %d", &a, &b);
	int ret=GCD(a, b);
	int m = (a * b) / ret;
	printf("最小公倍数=%d\n", m);
	return 0;
}

4.利用乘法思路

利用k/a=i， k/b=j，可以得到（a*i）% b==0,以此为循环条件

代码如下：

int main()
{
	long long a = 0;
	long long b = 0;
	while (scanf("%lld %lld", &a, &b) == 2)
	{
		//假设ab最小公倍数k
		//k/a=i
		// k/b=j
		//就有(a*i)%b==0
		int i = 1;
		while ((a * i) % b != 0)
		{
			i++;
		}
		//跳出循环的就是最小公倍数
		printf("%lld\n", a * i);
	}
	
	return 0;
}