隨筆 - 154  文章 - 60  trackbacks - 0
          <2008年2月>
          272829303112
          3456789
          10111213141516
          17181920212223
          2425262728291
          2345678

          聲明:

          該blog是為了收集資料,認(rèn)識朋友,學(xué)習(xí)、提高技術(shù),所以本blog的內(nèi)容除非聲明,否則一律為轉(zhuǎn)載!!

          感謝那些公開自己技術(shù)成果的高人們?。?!

          支持開源,尊重他人的勞動!!

          常用鏈接

          留言簿(3)

          隨筆分類(148)

          隨筆檔案(143)

          收藏夾(2)

          其他

          學(xué)習(xí)(技術(shù))

          觀察思考(非技術(shù))

          搜索

          •  

          最新評論

          閱讀排行榜

          評論排行榜

          Java算法——判斷素?cái)?shù)

          public static boolean isPrimeNumber(int number){
               if(number<2)
                   return false;
               for(int i=2;i<=Math.sqrt(number);i++){
                   if(number%i==0&&number!=2)
                       return false;
               }
               return true;
           }

          素?cái)?shù)算法(二)

          上次討論了簡單的素?cái)?shù)判定的算法,不過這個算法對于位數(shù)較大(一般小于108)的素?cái)?shù)判定就顯得相當(dāng)力不從心了。比如在素?cái)?shù)目前最廣泛的應(yīng)用領(lǐng)域-公共密鑰體系中,一般選擇的素?cái)?shù)都是相當(dāng)大的(通常在100位以上),如果采用上次的試除法來判定,那么可能要窮盡你一生的時(shí)間都還不夠。所以在一般的應(yīng)用領(lǐng)域,人們采用的是Rabin-Miller檢驗(yàn)法。下面是該檢驗(yàn)法的算法:

          首先選擇一個代測的隨機(jī)數(shù)p,計(jì)算b,b是2整除p-1的次數(shù)。然后計(jì)算m,使得n=1+(2^b)m。

          (1) 選擇一個小于p的隨機(jī)數(shù)a。
          (2) 設(shè)j=0且z=a^m mod p
          (3) 如果z=1或z=p-1,那麼p通過測試,可能使素?cái)?shù)
          (4) 如果j>0且z=1, 那麼p不是素?cái)?shù)
          (5) 設(shè)j=j+1。如果j<b且z<>p-1,設(shè)z=z^2 mod p,然后回到(4)。如果z=p-1,那麼p通過測試,可能為素?cái)?shù)。
          (6) 如果j=b 且z<>p-1,不是素?cái)?shù)

          數(shù)a被當(dāng)成證據(jù)的概率為75%。這意味著當(dāng)?shù)螖?shù)為t時(shí),它產(chǎn)生一個假的素?cái)?shù)所花費(fèi)的時(shí)間不超過1/4^t。實(shí)際上,對大多數(shù)隨機(jī)數(shù),幾乎99.99%肯定a是證據(jù)。

          實(shí)際考慮:

          在實(shí)際算法,產(chǎn)生素?cái)?shù)是很快的。

          (1) 產(chǎn)生一個n-位的隨機(jī)數(shù)p
          (2) 設(shè)高位和低位為1(設(shè)高位是為了保證位數(shù),設(shè)低位是為了保證位奇數(shù))
          (3) 檢查以確保p不能被任何小素?cái)?shù)整除:如3,5,7,11等等。有效的方法是測試小于2000的素?cái)?shù)。使用字輪方法更快
          (4) 對某隨機(jī)數(shù)a運(yùn)行Rabin-Miller檢測,如果p通過,則另外產(chǎn)生一個隨機(jī)數(shù)a,在測試。選取較小的a值,以保證速度。做5次 Rabin-Miller測試如果p在其中失敗,從新產(chǎn)生p,再測試。

          經(jīng)測試,這個算法在sun的Sparc II工作站上實(shí)現(xiàn):
          2 .8秒產(chǎn)生一個256位的素?cái)?shù)
          24.0秒產(chǎn)生一個512位的素?cái)?shù)
          2分鐘產(chǎn)生一個768位的素?cái)?shù)
          5.1分鐘產(chǎn)生一個1024位的素?cái)?shù)


          最近在網(wǎng)上看了不少關(guān)于素?cái)?shù)的問題,也學(xué)習(xí)到了不少東西,決定整理一下,算是一個學(xué)習(xí)的總結(jié)吧。

          首先想說明的是,雖然素?cái)?shù)可以進(jìn)行很深入的研究(如在RSA公共密鑰系統(tǒng)的應(yīng)用),但是由于我對數(shù)論的不甚熟悉,所以只能做一些淺嘗輒止的探討,主要就是對一些簡單的素?cái)?shù)相關(guān)算法進(jìn)行一個討論。

          首先來說說素?cái)?shù)的判定算法,如果你是讀譚浩強(qiáng)老師的《c程序設(shè)計(jì)》入門的話,那么一談到素?cái)?shù)的判定算法,你首先應(yīng)該想到的就是以下的算法:給定一個正整數(shù)n,用2到sqrt(n)之間的所有整數(shù)去除n,如果可以整除,則n不是素?cái)?shù),如果不可以整除,則n就是素?cái)?shù)。這個算法的時(shí)間復(fù)雜度十分明了,為O(sqrt(n)),算法的描述相當(dāng)簡單,實(shí)現(xiàn)也一樣不困難。

          # include <stdio.h>
          # include <math.h>

          int isPrime(int n)
          {
              int i ;
           
              for(i=2; i <= sqrt(n); i++){
                  if(n%i == 0 )
                      break ;
              }

              if(i <= sqrt(n))
                  printf("%d is not a prime ! ", &n) ;
              else
                  printf("%d is a prime ! ", &n) ;
           
              return 0 ;
          }


          =====================================
          public class  SuShu{  
           private int num; 
           SuShu(int n){   
            num=n;
           } 
           public  boolean isSuShu(){
            for(int i=2;i<num;i++){
             if(num%i==0)
              return false;                
            }    
             return true; 
           } 
           public static void main(String[] args){   
            for(int i=1;i<=100;i++){
             SuShu su=new SuShu(i);
             if(su.isSuShu())
              System.out.println(i+"是素?cái)?shù)");
             else
              System.out.println(i+"不是素?cái)?shù)");   
            }
           }
          }

          =============================

          /**  
          * @param n  
          * @return if n is a prime return true, else false  
          */ 
          public static boolean isPrime(int n) {
           // filte negative, zero, one   
           if (1 >= n) {
                 return false;
           }
           // 2 is a prime, stop filter   
           if (2 == n) {
            return true;
           }
           // filter evens
           if (0 == n % 2) {
            return false;
           }
           // go on filting...   
           for (int a = 3; a <= Math.sqrt(n); a += 2) {
            if (0 == n % a) {
             return false;
            }
           }
           // the rest is all prime, stop filting   
           return true;
          }
          ==============================
          //目前我認(rèn)為最好的辦法是:(不是lk的觀點(diǎn))
          public boolean isPrime(int n){
              for(int i = 2; i * i <= n; i++){
            if(n % i == 0)
             return false;
            }
              return true;
          }
          ===============================
          素?cái)?shù)是這樣的整數(shù),它除了能表示為它自己和1的乘積以外,不能表示為任何其它兩個整數(shù)的乘積。例如,15=3*5,所以15不是素?cái)?shù);又如,12=6*2=4*3,所以12也不是素?cái)?shù)。另一方面,13除了等于13*1以外,不能表示為其它任何兩個整數(shù)的乘積,所以13是一個素?cái)?shù)。
          有的數(shù),如果單憑印象去捉摸,是無法確定它到底是不是素?cái)?shù)的。有些數(shù)則可以馬上說出它不是素?cái)?shù)。一個數(shù),不管它有多大,只要它的個位數(shù)是2、4、5、6、8或0,就不可能是素?cái)?shù)。此外,一個數(shù)的各位數(shù)字之和要是可以被3整除的話,它也不可能是素?cái)?shù)。但如果它的個位數(shù)是1、3、7或9,而且它的各位數(shù)字之和不能被3整除,那么,它就可能是素?cái)?shù)(但也可能不是素?cái)?shù))。沒有任何現(xiàn)成的公式可以告訴你一個數(shù)到底是不是素?cái)?shù)。你只能試試看能不能將這
          個數(shù)表示為兩個比它小的數(shù)的乘積。

          代碼如下:

          package com.vo;

          public class Sushu {


           public static void main(String[] args) {
            int s=0;
            int i;
            for(i=0;i<=100;i++)
            {
           int j;
           for(j=2;j<=i;j++){
            if(i%j==0)
             break;
           }
           if(i==j)
            System.out.println(i);
            }

           }

          }

           

          posted on 2008-02-01 11:19 lk 閱讀(5203) 評論(0)  編輯  收藏 所屬分類: j2se
          主站蜘蛛池模板: 大安市| 阳泉市| 舞阳县| 邵阳县| 深水埗区| 新丰县| 定边县| 克拉玛依市| 巩义市| 揭阳市| 望城县| 沁阳市| 邵阳市| 广灵县| 普安县| 满洲里市| 西藏| 湖州市| 岗巴县| 象山县| 漾濞| 连江县| 独山县| 青龙| 剑阁县| 两当县| 河北区| 丰镇市| 青岛市| 麻城市| 双峰县| 崇左市| 宁远县| 平原县| 阳西县| 宁津县| 永济市| 江城| 恩平市| 利津县| 贡山|