posts - 73,  comments - 55,  trackbacks - 0
          一,兩個數的最大公約數:

          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++語言描述為:

          void swap(int & a, int & 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 > b){
                   swap(a,b);
               }
               int c;
               for(c = a % b ; c > 0 ; c = a % b){
                     a = b;
                     b = c;
               }
               return b;
          }

          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 實現

          // c++/java stein 算法
          int gcd(int a,int b){
               if(a<b){
          //arrange so that a>b
                   int temp = a;
                     a = b;
                     b=temp;
               }
               if(0==b)
          //the base case
                  return a;
               if(a%2==0 && 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
          }

          二,多個數的最大公約數:(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
          posted on 2007-12-15 15:40 保爾任 閱讀(4683) 評論(2)  編輯  收藏 所屬分類: Arithmetic & Data Structure

          FeedBack:
          # re: 求兩個數或多個數的最大公約數算法及其實現
          2008-02-16 02:20 | no name
          傳說 歐幾里德算法 一行就可以搞定了
          int gcd(int a,int b){return b==0?a:gcd(b,a%b);}  回復  更多評論
            
          # re: 求兩個數或多個數的最大公約數算法及其實現
          2008-02-16 02:22 | 偶爾郁悶
          對于N個數的話……做N-1次歐幾里德應該會更快些

          你這種做法 如果有100000個數 分別是1000000 或 2000000 那將是很恐怖的事情
            回復  更多評論
            

          <2007年12月>
          2526272829301
          2345678
          9101112131415
          16171819202122
          23242526272829
          303112345

          常用鏈接

          留言簿(4)

          隨筆分類

          隨筆檔案

          文章分類

          文章檔案

          搜索

          •  

          最新評論

          閱讀排行榜

          評論排行榜

          主站蜘蛛池模板: 柞水县| 缙云县| 宜州市| 开江县| 乌鲁木齐市| 淳化县| 阿图什市| 土默特左旗| 皮山县| 重庆市| 蓬安县| 东台市| 昌吉市| 治县。| 杭州市| 隆昌县| 绥滨县| 永胜县| 进贤县| 安龙县| 沧州市| 乳山市| 福泉市| 宁武县| 舟山市| 万宁市| 河北省| 乌兰浩特市| 博罗县| 宜良县| 安康市| 林芝县| 巴青县| 桐梓县| 镇康县| 修武县| 逊克县| 伽师县| 龙川县| 浙江省| 乐东|