1. 歐幾里德算法

歐幾里德算法又稱輾轉(zhuǎn)相除法， 用于計(jì)算兩個(gè)整數(shù)a, b的最大公約數(shù)。其計(jì)算原理依賴于下面的定理：
定理： gcd(a, b) = gcd(b, a mod b)

證明：
  a可以表示成a = kb + r, 則r = a mod b
  假設(shè)d是a, b的一個(gè)公約數(shù)， 則有  d|a, d|b, 而r = a - kb, 因此d|r。
  因此，d是(b, a mod b)的公約數(shù)。
  加上d是(b，a mod b)的公約數(shù)，則d|b, d|r, 但是a = kb + r,因此d也是(a, b)的公約數(shù)。
  因此，(a, b) 和(a, a mod b)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證。

歐幾里德的Python語言描述為：

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算法
歐幾里德算法是計(jì)算兩個(gè)數(shù)最大公約數(shù)的傳統(tǒng)算法，無論是理論，還是從效率上都是很好的。但是他有一個(gè)致命的缺陷，這個(gè)缺陷只有在很大的素?cái)?shù)時(shí)才會(huì)顯現(xiàn)出來。
考慮現(xiàn)在的硬件平臺(tái)，一般整數(shù)最多也就是64位， 對于這樣的整數(shù)，計(jì)算兩個(gè)數(shù)值就的模很簡單的。對于字長為32位的平臺(tái)，計(jì)算兩個(gè)不超過32位的整數(shù)的模，只需要一個(gè)指令周期，而計(jì)算64位以下的整數(shù)模，也不過幾個(gè)周期而已。但是對于更大的素?cái)?shù)，這樣的計(jì)算過程就不得不由用戶來設(shè)計(jì)，為了計(jì)算兩個(gè)超過64位的整數(shù)的模，用戶也許不得不采用類似于多位除法手算過程中的試商法，這個(gè)過程不但復(fù)雜，而且消耗了很多CPU時(shí)間。對于現(xiàn)代密碼算法，要求計(jì)算128位以上的素?cái)?shù)的情況比比皆是，設(shè)計(jì)這樣的程序迫切希望能夠拋棄除法和取模。
Stein算法由J.Stein 1961年提出，這個(gè)方法也是計(jì)算兩個(gè)數(shù)的最大公約數(shù)。和歐幾里德算法不同的是，Stein算法只有整數(shù)的移位和加減法，這對于程序設(shè)計(jì)者是一個(gè)福音。
為了說明Stein算法的正確性，首先必須注意到以下結(jié)論：
  gcd(a, a) = a， 也就是一個(gè)數(shù)和他自己的公約數(shù)是其自身。
  gcd(ka, kb) = k * gcd(a, b)，也就是最大公約數(shù)運(yùn)算和倍乘運(yùn)算可以交換，特殊的，當(dāng)k=2時(shí)，說明兩個(gè)偶數(shù)的最大公約數(shù)比如能被2整除。
Stein算法的python實(shí)現(xiàn)如下：

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. 一般求解實(shí)現(xiàn)

核心代碼很簡單：

def gcd(a, b):if b == 0:return areturn gcd(b, a % b)

附上一個(gè)用Python實(shí)現(xiàn)求最大公約數(shù)同時(shí)判斷是否是素?cái)?shù)的一般方法：
程序如下:

#!/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跳出時(shí)會(huì)跳出下面的else語句     count -= 1   else:     print num, "is prime"  for eachNum in range(10,21):   showMaxFactor(eachNum) 

輸出如下:

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