計算最大公因數(shù)的歐幾里得算法

最大公因數(shù)

最大公因數(shù)，也稱最大公約數(shù)，指兩個或多個整數(shù)共有約數(shù)中最大的一個。a，b的最大公約數(shù)記為（a，b）。求最大公約數(shù)有多種方法，常見的有質(zhì)因數(shù)分解法、輾轉(zhuǎn)相除法等等。

歐幾里得算法

歐幾里德算法又稱輾轉(zhuǎn)相除法，是指用于計算兩個正整數(shù)a，b的最大公約數(shù)。應(yīng)用領(lǐng)域有數(shù)學(xué)和計算機兩個方面。計算公式gcd(a,b) = gcd(b,a mod b)。歐幾里得算法在RSA加密算法中有運用。

源碼

//當(dāng)N>M時，第一次循環(huán)之后兩數(shù)將進行交換

int Gcd(int m,int n){

? ? int r;

? ? while(n > 0){

? ? ? ? r = m % n;

? ? ? ? m = n;

? ? ? ? n = r;

? ? }

? ? return m;

}

算法分析

算法通過連續(xù)計算余數(shù)，知道余數(shù)是0為止，最后所得的非0余數(shù)就是最大公因數(shù)。例如 M=1989 ，N=1590，則余數(shù)序列為399，393，6，3，0。因而，Gcd(1989,1590)=3，從余數(shù)的序列可知，這是一個快速收斂的算法。要想得出該算法的運行時間，就需要確定余數(shù)序列究竟有多長？不妨大膽的猜測log(N)看似是非常理想的答案，但是余數(shù)序列遞減的規(guī)律并非是按照常數(shù)因子所遞減的，事實上，數(shù)學(xué)家們已經(jīng)證明了，在兩次迭代以后，余數(shù)的值最多是原始值的一半。由此可知，迭代次數(shù)之多是2log(N) = O(logN)從而得到算法的時間復(fù)雜度。下面，我們從數(shù)學(xué)家那里問來了證明過程。

時間復(fù)雜度證明

定理：

如果 M > N ，則 M mod N < M/2

證明：如果 N<=M/2 ，則余數(shù)小于N，故定理在這種情況下成立

如果 N>M/2 ，此時M僅含有一個N，從而余數(shù)為M-N

從上面的例子來看，2logN 大約是20，但是實際上，我們只是運行了7次計算，可能有人會說，這個常數(shù)2不是最好的界限值。事實上，歐幾里得算法的平均時間復(fù)雜度是需要大量的數(shù)學(xué)分析進行證明的，算法迭代的平均次數(shù)是（12ln2lnN）/pi^2+1.47。

有興趣的同學(xué)可以研究一下質(zhì)因數(shù)分解等其他算法哦