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