Java算法——判斷素數

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

素數算法（二）

上次討論了簡單的素數判定的算法，不過這個算法對于位數較大（一般小于108）的素數判定就顯得相當力不從心了。比如在素數目前最廣泛的應用領域-公共密鑰體系中，一般選擇的素數都是相當大的（通常在100位以上），如果采用上次的試除法來判定，那么可能要窮盡你一生的時間都還不夠。所以在一般的應用領域，人們采用的是Rabin-Miller檢驗法。下面是該檢驗法的算法：

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

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

數a被當成證據的概率為75%。這意味著當迭代次數為t時，它產生一個假的素數所花費的時間不超過1/4^t。實際上，對大多數隨機數，幾乎99.99%肯定a是證據。

實際考慮：

在實際算法，產生素數是很快的。

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

經測試，這個算法在sun的Sparc II工作站上實現：
2 .8秒產生一個256位的素數
24.0秒產生一個512位的素數
2分鐘產生一個768位的素數
5.1分鐘產生一個1024位的素數

最近在網上看了不少關于素數的問題，也學習到了不少東西，決定整理一下，算是一個學習的總結吧。

首先想說明的是，雖然素數可以進行很深入的研究（如在RSA公共密鑰系統的應用），但是由于我對數論的不甚熟悉，所以只能做一些淺嘗輒止的探討，主要就是對一些簡單的素數相關算法進行一個討論。

首先來說說素數的判定算法，如果你是讀譚浩強老師的《c程序設計》入門的話，那么一談到素數的判定算法，你首先應該想到的就是以下的算法：給定一個正整數n，用2到sqrt(n)之間的所有整數去除n，如果可以整除，則n不是素數，如果不可以整除，則n就是素數。這個算法的時間復雜度十分明了，為O（sqrt（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+"是素數");
   else
    System.out.println(i+"不是素數");   
  }
 }
}

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

/**  
* @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;
}
==============================
//目前我認為最好的辦法是:(不是lk的觀點)
public boolean isPrime(int n){
    for(int i = 2; i * i <= n; i++){
  if(n % i == 0)
   return false;
  }
    return true;
}
===============================
素數是這樣的整數，它除了能表示為它自己和1的乘積以外，不能表示為任何其它兩個整數的乘積。例如，15＝3＊5，所以15不是素數；又如，12＝6＊2＝4＊3，所以12也不是素數。另一方面，13除了等于13＊1以外，不能表示為其它任何兩個整數的乘積，所以13是一個素數。
有的數，如果單憑印象去捉摸，是無法確定它到底是不是素數的。有些數則可以馬上說出它不是素數。一個數，不管它有多大，只要它的個位數是2、4、5、6、8或0，就不可能是素數。此外，一個數的各位數字之和要是可以被3整除的話，它也不可能是素數。但如果它的個位數是1、3、7或9，而且它的各位數字之和不能被3整除，那么，它就可能是素數（但也可能不是素數）。沒有任何現成的公式可以告訴你一個數到底是不是素數。你只能試試看能不能將這
個數表示為兩個比它小的數的乘積。

代碼如下：

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

 }

}