求最大公約數和最小公倍數（遞迴演算法及非遞迴演算法）

輾轉相除法基於如下原理：兩個整數的最大公約數等於其中較小的數和兩數的相除餘數的最大公約數。

例如，252和105的最大公約數是21（252 = 21 × 12；105 = ... 求最大公約數和最小公倍數（遞迴演算法及非遞迴演算法） 首頁 最新 HTML CSS JavaScript jQuery Python3 Python2 Java C C++ Go SQL 首頁 最新 Search 求最大公約數和最小公倍數（遞迴演算法及非遞迴演算法） 2019-02-08254 最近做題目發現一些題目需要求數的最大公約數和最小公倍數，想想最大公約數和最小公倍數平時做數學的時候感覺不是很難，但是突然要程式設計來實現，卻一下子不知所措了，後來看了下別人寫的，發現其實也不算特別難。

最小公倍數其實只要一個公式，即整數A和整數B的最小公倍數為A*B/gcd(A,B)（gcd(A,B)為A和B的最大公約數），可見A和B的最小公倍數就為A和B的乘積再除以它倆的最大公約數，也就是說最終還是要求最大公約數，所以以下主要討論最大公約數演算法。

最大公約數的演算法原來還分為兩種，一種是用非遞迴的演算法，一種是遞迴的演算法。

遞迴的演算法在二叉樹裡面是很常見的，以及斐波那契數列的實現上，對於遞迴演算法的優點就是程式碼可以極其簡短，缺點則是需要不斷呼叫函式，效率不用直接用迴圈。

無論是通過遞迴還是非遞迴的方法，一下的程式碼都是基於一種求兩個數最大公約數的演算法——輾轉相除法。

輾轉相除法基於如下原理：兩個整數的最大公約數等於其中較小的數和兩數的相除餘數的最大公約數。

例如，252和105的最大公約數是21（252=21× 12；105=21×5）；因為252/105=2餘42，所以105和42的最大公約數也是21。

在這個過程中，較大的數縮小了，所以繼續進行同樣的計算可以不斷縮小這兩個數直至餘數變為零。

這時的除數就是所求的兩個數的最大公約數。

以下是求最大公約數遞迴演算法 //最大公約數（遞迴演算法） intgcd(intx,inty){ if(y==0) returnx; else returngcd(y,x%y); }從上面可以看出，遞迴演算法極其簡短，而下面的非遞迴演算法相對則長一點。

//最大公約數（非遞迴演算法） intgcd(intx,inty){ intmax,min,temp; max=x>y?x:y; min=x