求最大公約數(shù)，公元前300年歐幾里得的方法，遠(yuǎn)比老師教的簡單

“求最大公約數(shù)”，聽到這幾個字，是不是覺得腦袋瓜子“嗡嗡”的，好像一瞬之間就被拽回了學(xué)生時代。

對于一些人而言，學(xué)生時代可以算得上是一場綿長的噩夢，所以在醒來之后，便把夢中的一切都拋之腦后了，至于“最大公約數(shù)”是什么，也早已不記得了，那就讓我們來回憶一下。現(xiàn)在假設(shè)有兩個整數(shù)，分別是A和B，如果A除以B之后得到的仍然是一個整數(shù)，那么我們就稱A為“B的倍數(shù)”，稱B為“A的約數(shù)”，而A和B這兩個數(shù)字的最大公共約數(shù)就是“最大公約數(shù)”。

那么如何求得兩個數(shù)字的最大公約數(shù)呢？已經(jīng)記不得求解最大公約數(shù)的知識是小學(xué)學(xué)習(xí)的，還是初中教授的了，但求解最大公約數(shù)的方法，你一定記得，即便是不記得了，只要一聽到就會覺得似曾相識，那就是“分解質(zhì)因數(shù)”。

對于“分解質(zhì)因數(shù)”這個詞，所有人應(yīng)該都有所印象，但至于什么是分解質(zhì)因數(shù)，如何分解質(zhì)因數(shù)，恐怕就沒有幾個人記得了。不過不記得也不要緊，既然忘了，就讓它忘卻吧，因為通過分解質(zhì)因數(shù)的方法求得最大公約數(shù)實在是過于繁瑣了，而且效率不高。

現(xiàn)在我們要來說一種非常簡單且效率極高的方法，不過這并不是什么新方法，而是早在公元前300年就已經(jīng)出現(xiàn)了，著名的古希臘數(shù)學(xué)家歐幾里得將這種方法記載在了《幾何原本》之中，而現(xiàn)在我們就將這種方法稱之為輾轉(zhuǎn)相除法，如果我們在小學(xué)的時候就知道了這種方法，那么一定能夠成為班級里的“最大公約數(shù)之王”?，F(xiàn)在我們就舉一個實例來介紹這種簡單的方法，隨便選兩個數(shù)字，110和24。

要求110和24的最大公約數(shù)，用不著去分解質(zhì)因數(shù)，只需要通過幾步簡單的除法就可以了。

首先我們用110除以24，所得到的商是4，而余數(shù)是14。接下來我們用剛才的除數(shù)24除以余數(shù)14，所得到的商是1，余數(shù)是10。第三步用上一步的除數(shù)14除以余數(shù)10，得到商是1，余數(shù)是4。第四步用第三步的除數(shù)10除以余數(shù)4，得到商是2，余數(shù)是2。最后一步，還是用上一步的除數(shù)4除以余數(shù)2，得到商是2，余數(shù)為0。余數(shù)為0就不可以再繼續(xù)計算了，所以最終的商2就是110和24的最大公約數(shù)。

就是如此簡單，只需要學(xué)會加減乘除就可以高效率地計算最大公約數(shù)，而用不著去搞什么分解質(zhì)因數(shù)。歐幾里得的方法固然簡單，但現(xiàn)實中總有些人對于數(shù)字不太感冒，那也沒有關(guān)系，靠畫圖同樣可以求解最大公約數(shù)。

還是以110和24兩個數(shù)字為例，要通過圖解法來求最大公約數(shù)，首先我們就要畫出一個長方形，這個長方形的長為110，而寬為24。

現(xiàn)在我們要做的就是用大量一模一樣的正方形將這個長方形填滿，而能夠恰好將這個長方形填滿的最大的正方形就是這兩個數(shù)字的最大公約數(shù)?，F(xiàn)在問題來了，如何能夠找到最大的且剛好可以將這個長方形填滿的正方形呢？首先我們先在這個長方形的一邊放入一個邊長為24的正方形，而剩余的空間為長86、寬24的長方形。之后再放入一個邊長24的正方形，剩余的空間為長62、寬24。繼續(xù)放入邊長24的正方形，剩余空間為長38、寬24。最后再放入一個邊長24的正方形，剩余空間為14x24。

現(xiàn)在已經(jīng)放不下邊長為24的正方形了，所以我們放入一個邊長為14的正方形，剩余空間為14X10。

邊長為14的正方形也放不下了，于是我們只能放入一個邊長為10的正方形，剩余空間為4X10。

現(xiàn)在能夠放下邊長為4的正方形了，我們放入兩個，這樣就剩下了一個4X2的區(qū)域，在這個區(qū)域之中放入兩個邊長為2的正方形，剛好可以將其填滿。現(xiàn)在我們就知道了，能夠恰好將這個長方形填滿的最大的正方形就是邊長為2的正方形，所以2就是110和24的最大公約數(shù)，這個結(jié)果與歐幾里得的輾轉(zhuǎn)相除法所得的結(jié)果是完全一樣的。

既然有如此簡單直觀、效率又高的方法，為什么老師還要讓我們通過分解質(zhì)因數(shù)的方法來求最大公約數(shù)呢？其實原因很簡單，我們在上學(xué)的時候所學(xué)的很多知識并不是用于解決問題的，而是用來鍛煉思維的，如果我們企圖用學(xué)校學(xué)的知識來解決實際問題，你可能會發(fā)現(xiàn)這個世界太過復(fù)雜了。

更多內(nèi)容請關(guān)注公眾號：sunmonarch