提示：文章寫完后，目錄可以自動生成，如何生成可參考右邊的幫助文檔

題目內(nèi)容

正整數(shù)A和正整數(shù)B的最小公倍數(shù)是指 能被A和B整除的最小的正整數(shù)值,設(shè)計(jì)一個(gè)算法，求A,B的最小公倍數(shù)

輸入：

輸入兩個(gè)正整數(shù)A,B

輸出：

輸出:A,B的最小公倍數(shù)

一、題目解讀

1、最小公倍數(shù)（LCM）是：能被A和B整除的最小的正整數(shù)
2、如何求最小公倍數(shù)：
思路一：
最小公倍數(shù)一定是兩個(gè)數(shù)中較大的值。
加法尋找：讓較大的值賦值給m，利用m可以整除A和B來判斷。如果m一次可以整除A和B就找到了最小公倍數(shù)，否則就m+1看下一位數(shù)是否可以整除A和B（需要循環(huán)）;
乘法尋找：不用判斷a,b誰為較大值，利用循環(huán)變量i（1-無窮），如果 a * i % b == 0或者 b * i % a== 0,就找到了最小公倍數(shù)a * i或b * i

思路二：
利用輾轉(zhuǎn)相除法求出最大公約數(shù)，再（a*b）/ 最大公約數(shù)=最小公倍數(shù)

思路三：假設(shè)a,b最小公倍數(shù)為k，k/a=i,k/b=j.就有(a*i)%b==0,
利用此條件為循環(huán)條件，求出最小公倍數(shù).

最大公約數(shù)博客

二、代碼實(shí)現(xiàn)

1.加法尋找最小公倍數(shù)

如果找到最小公倍數(shù)就返回t，沒找到就t++找下一個(gè)數(shù)是否成立。
代碼如下（示例）：

//加法
int LCM(int a, int b)
{
	int t = 0;
	//將兩個(gè)數(shù)中較大的給t
    //int t=a>b?a:b;三目操作符運(yùn)算求兩個(gè)中較大值
	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;
	//將兩個(gè)數(shù)中較大的給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("最小公倍數(shù)=%d\n", ret);
	return 0;
}

2.乘法尋找最小公倍數(shù)

發(fā)現(xiàn)最小公倍數(shù)只能是兩數(shù)中其中一個(gè)的整倍數(shù)，所以t是a,b中一個(gè)，t=t*i -> 如果得到的數(shù)可以整除a和b，則為最小公倍數(shù)；
代碼如下（示例）：

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

上述代碼重復(fù)太多，很多可以省去，代碼改進(jìn)如下

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;
	//最小公倍數(shù)最大可能就是兩數(shù)相乘
	/*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("最小公倍數(shù)=%d\n", ret);
	return 0;
}

3、輾轉(zhuǎn)相除法求解最小公倍數(shù)

輾轉(zhuǎn)相除法求出最大公約數(shù)，(a*b)/最大公約數(shù)==最小公倍數(shù)

#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("最小公倍數(shù)=%d\n", m);
	return 0;
}

4.利用乘法思路

利用k/a=i， k/b=j，可以得到（a*i）% b==0,以此為循環(huán)條件

代碼如下：

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

總結(jié)

利用代碼解決問題，通過上述練習(xí)，希望能增強(qiáng)自己的邏輯思維，考慮的全面性，加強(qiáng)C語言的練習(xí)，讓代碼更優(yōu)化。文章來源地址http://www.zghlxwxcb.cn/news/detail-462023.html

到了這里，關(guān)于最小公倍數(shù)求法 (3種代碼思路供參考 ) --（C語言實(shí)現(xiàn)）-- 詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！