作者主頁：paper jie的博客_CSDN博客-C語言,算法詳解領(lǐng)域博主

本文作者：大家好，我是paper jie，感謝你閱讀本文，歡迎一建三連哦。

本文錄入于《算法詳解》專欄，本專欄是針對于大學生，編程小白精心打造的。筆者用重金(時間和精力)打造，將算法基礎(chǔ)知識一網(wǎng)打盡，希望可以幫到讀者們哦。

其他專欄：《系統(tǒng)解析C語言》《C語言》《C語言-語法篇》

內(nèi)容分享：本期將對求最小公倍數(shù)和最大公因數(shù)進行詳細的講解，各位看官姥爺快搬好小板凳坐好叭。

? ? -------- 不要998，不要98，只要一鍵三連，三連買不了吃虧，買不了上當

目錄

最大公約數(shù)和最小公倍數(shù)的定義

實現(xiàn)的基本思想

具體代碼

最大公約數(shù)和最小公倍數(shù)的定義

如果數(shù)a能被數(shù)b整除，a就叫做b的倍數(shù)，b就叫做a的約數(shù)。約數(shù)和倍數(shù)都表示一個整數(shù)與另一個整數(shù)的關(guān)系，不能單獨存在。如只能說16是某數(shù)的倍數(shù)，2是某數(shù)的約數(shù)，而不能孤立地說16是倍數(shù)，2是約數(shù)。最大公約數(shù)就是最大的約數(shù)。公倍數(shù)是指在兩個或兩個以上的 自然數(shù) 中，如果它們有相同的 倍數(shù) ，這些倍數(shù)就是它們的公倍數(shù)。 公倍數(shù)中最小的，就稱為這些 整數(shù) 的 最小公倍數(shù)

實現(xiàn)的基本思想

求最大公因數(shù)我們采用輾轉(zhuǎn)相除法。什么是輾轉(zhuǎn)相除法呢？

在數(shù)學中，輾轉(zhuǎn)相除法，又稱歐幾里得算法，是求取最大公約數(shù)的一種算法。輾轉(zhuǎn)相除法首次出現(xiàn)于歐幾里得的《幾何原本》中的第Ⅶ卷，書中的命題ⅰ和命題ⅱ所描述的就是輾轉(zhuǎn)相除法，而在中國，輾轉(zhuǎn)相除法最早出現(xiàn)在《九章算法》中。它有一個經(jīng)典的幾何描述：

輾轉(zhuǎn)相除法既然起源于希臘，那么就從希臘開始講起，希臘人非常喜歡從圖形或者說是用幾何的角度去看待問題，很多問題希臘數(shù)學家都習慣先去思考能否將其轉(zhuǎn)化為直觀的幾何問題再進行求解，希臘數(shù)學家甚至認為：所有的數(shù)字都與一個幾何概念有關(guān)系。我們今天所說的「有理數(shù)」和「無理數(shù)」這兩個概念，英文是將其翻譯成「Rational number」和「Irrantional number」的，而這兩個單詞的拉丁文詞源（Ratio）的原意則是成比例的意思。所以很自然地，希臘數(shù)學家在面對求兩數(shù)的最大公約數(shù)這個問題的時候，也首先去思考這個問題是否能通過將其轉(zhuǎn)化成一個幾何問題來處理。在經(jīng)過一些嘗試之后，這一設想最終實現(xiàn)了，希臘數(shù)學家是這樣處理的，將所要求取最大公約數(shù)的兩個數(shù)字A、B分別作為矩形的兩條邊，就形成了一個矩形，這樣，原來的問題就被轉(zhuǎn)化了。

還記得最大公約數(shù)的定義嗎？所謂最大公約數(shù)，就是指兩個數(shù)字所共同擁有的約數(shù)中最大的那一個。這種描述是以數(shù)字的方式進行描述的，這種數(shù)字形式的描述太過抽象，使人不好理解，因為人類數(shù)十萬年來的生活導致人類的認知方式會更偏向於圖形這種更加直觀的方式。那么現(xiàn)在問題就變成了：如何將最大公約數(shù)問題從用數(shù)字進行描述，轉(zhuǎn)化為圖形或者說幾何形式的描述。希臘數(shù)學家是這樣處理的，即：以所要求取最大公約數(shù)的兩個數(shù)字為邊構(gòu)造一個矩形，然后嘗試在這個矩形中去找到這樣一個正方形，這類正方形能夠沒有縫隙的鋪滿上述矩形，很明顯，這類正方形有很多個的（這里只考慮正整數(shù)邊長），而我們的目標就是找出這類正方形中最大的那一個。所以問題現(xiàn)在就又轉(zhuǎn)化成了：該怎么找到這樣一個正方形？

希臘數(shù)學家是這樣處理的，在我們預先構(gòu)造的矩形中，我們先以矩形的短邊構(gòu)造正方形，然后再去計算這樣的正方形可以在大矩形中「最多」放置多少個，這個計算過程可以用取余的方式進行計算。接下來，我們再用長邊余下的長度構(gòu)建正方形，在去試圖鋪滿剩下未被覆蓋的部分，然后計算這個正方形最多可以放置幾個，直到我們找到這樣一個正方形，這個正方形可以完全鋪滿整個大矩形。那么這個正方形就是我們最終要找的答案，自然而然的，這個正方形的邊長也就是我們要找的兩數(shù)的最大公約數(shù)。

輾轉(zhuǎn)相除法之所以有效是因為其基于一個核心原理，即：兩個數(shù)的最大公約數(shù)等于其中較小的數(shù)字和二者之間余數(shù)的最大公約數(shù)為了更容易理解，可以對這句話進行簡單的分析，以m和n舉例：m%n!=0的話，將n的值賦給m，m%n的余數(shù)賦給n。這樣是一次循環(huán)，后面一直循環(huán)以上步驟直到m%n==0，這時n里面的值就是最大公因數(shù)。

求最小公倍數(shù)我們可以用一個公式：m*n/最大公因數(shù)?

因為 最大公因數(shù)*最小公倍數(shù) = m * n，所以我們知道其中一個就可以求出另一個了。

具體代碼

注意：這里m和n的大小其實不用糾結(jié)，因為m%n時它們的位置就會變的正常，比如：m=2 n=3 它們一旦采用輾轉(zhuǎn)相除法，就會變成m=3 n=2.

int main()
{
	int m = 0;
	int n = 0;
	//要輸入的值
	scanf("%d %d", &m, &n);
	//用a b另存一份m n的值，等下求最小公倍數(shù)可以用
	int a = m;
	int b = n;
	//m%n==0 時跳出
	while (m % n != 0)
	{
		int tmp = m % n;
		m = n;
		n = tmp;
	}
	printf("最大公因數(shù)=%d\n", n);
	//最大公約數(shù)*最小公倍數(shù)=m*n
	//知一個就可以求另一個
	printf("最小公倍數(shù)=%d\n", a * b / n);
	return 0;
}

?文章來源地址http://www.zghlxwxcb.cn/news/detail-548917.html

到了這里，關(guān)于C語言—最大公約數(shù)和最小公倍數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！