兩個數的最大公約數

一，兩個數的最大公約數：

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)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證

歐幾裡德算法就是根據這個原理來做的，其算法用C++語言描述為：

<code>voidswap(int&amp; a, int &amp; b){      int c = a;        a = b;        b = c; } int gcd(int a,int b){      if(0 == a ){          return b;      }      if( 0 == b){          return a;      }      if(a &gt; b){          swap(a,b);      }      int c;      for(c = a % b ; c&gt; 0 ; c = a % b){            a = b;            b = c;      }      return b; }</code>

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整除

C++/java 實作

<code>// c++/java stein 算法 int gcd(int a,int b){      if(a&lt;b){//arrange so that a&gt;b          int temp = a;            a = b;            b=temp;      }      if(0==b)//the base case         return a;      if(a%2==0&amp;&amp; b%2==0)//a and b are even          return 2*gcd(a/2,b/2);      if ( a%2== 0)// only a is even          return gcd(a/2,b);      if ( b%2==0)// only b is even          return gcd(a,b/2);      return gcd((a+b)/2,(a-b)/2);// a and b are odd }</code>

二，多個數的最大公約數：(python實作：取出數組a中最小的，從2到最小的循環，找出其中最大的能被數組中所有數整除的那個數，就是最大公約數)

def gcd(a):

    a.sort()

    min = a[0]

    result = 1

    for i in range(2, min+1):

        flag = True

        for j in a:

            if j % i != 0:

                flag = False

        if flag == True:

            result = i

    return result