1. 歐幾里德算法
歐幾里德算法又稱輾轉相除法， 用于計算兩個整數a, b的最大公約數。其計算原理依賴于下面的定理：
定理： gcd(a, b) = gcd(b, a mod b)
證明：
a可以表示成a = kb + r, 則r = a mod b
假設d是a, b的一個公約數， 則有 d|a, d|b, 而r = a - kb, 因此d|r。
因此，d是(b, a mod b)的公約數。
加上d是(b，a mod b)的公約數，則d|b, d|r, 但是a = kb + r,因此d也是(a, b)的公約數。
因此，(a, b) 和(a, a mod b)的公約數是一樣的，其最大公約數也必然相等，得證。
歐幾里德的Python語言描述為：
|
1
2
3
4
5
6
7
8
9
10
|
def gcd(a, b): if a < b: a, b = b, a while b != 0: temp = a % b a = b b = temp return a |
2. Stein算法
歐幾里德算法是計算兩個數最大公約數的傳統算法，無論是理論，還是從效率上都是很好的。但是他有一個致命的缺陷，這個缺陷只有在很大的素數時才會顯現出來。
考慮現在的硬件平臺，一般整數最多也就是64位， 對于這樣的整數，計算兩個數值就的模很簡單的。對于字長為32位的平臺，計算兩個不超過32位的整數的模，只需要一個指令周期，而計算64位以下的整數模，也不過幾個周期而已。但是對于更大的素數，這樣的計算過程就不得不由用戶來設計，為了計算兩個超過64位的整數的模，用戶也許不得不采用類似于多位除法手算過程中的試商法，這個過程不但復雜，而且消耗了很多CPU時間。對于現代密碼算法，要求計算128位以上的素數的情況比比皆是，設計這樣的程序迫切希望能夠拋棄除法和取模。
Stein算法由J.Stein 1961年提出，這個方法也是計算兩個數的最大公約數。和歐幾里德算法不同的是，Stein算法只有整數的移位和加減法，這對于程序設計者是一個福音。
為了說明Stein算法的正確性，首先必須注意到以下結論：
gcd(a, a) = a， 也就是一個數和他自己的公約數是其自身。
gcd(ka, kb) = k * gcd(a, b)，也就是最大公約數運算和倍乘運算可以交換，特殊的，當k=2時，說明兩個偶數的最大公約數比如能被2整除。
Stein算法的python實現如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
def gcd_Stein(a, b): if a < b: a, b = b, a if (0 == b): return a if a % 2 == 0 and b % 2 == 0: return 2 * gcd_Stein(a/2, b/2) if a % 2 == 0: return gcd_Stein(a / 2, b) if b % 2 == 0: return gcd_Stein(a, b / 2) return gcd_Stein((a + b) / 2, (a - b) / 2) |
3. 一般求解實現
核心代碼很簡單：
|
1
2
3
|
def gcd(a, b):if b == 0:return areturn gcd(b, a % b) |
附上一個用Python實現求最大公約數同時判斷是否是素數的一般方法：
程序如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#!/usr/bin/env python def showMaxFactor(num): count = num / 2 while count > 1: if num % count == 0: print 'largest factor of %d is %d' % (num, count) break #break跳出時會跳出下面的else語句 count -= 1 else: print num, "is prime" for eachNum in range(10,21): showMaxFactor(eachNum) |
輸出如下:
|
1
2
3
4
5
6
7
8
9
10
11
|
largest factor of 10 is 511 is primelargest factor of 12 is 613 is primelargest factor of 14 is 7largest factor of 15 is 5largest factor of 16 is 817 is primelargest factor of 18 is 919 is primelargest factor of 20 is 10 |
