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);
  }

 }

}