大家好，我是平頭哥，今天給大家分享的內(nèi)容為如何求質(zhì)數(shù)。
什么是質(zhì)數(shù)
百度百科上說質(zhì)數(shù)（prime number）又稱素數(shù)办成，有無限個。(話說prime number不應(yīng)該翻譯成主要數(shù)嘛)搂漠。
質(zhì)數(shù)的定義
質(zhì)數(shù)又稱素數(shù)迂卢。一個大于1的自然數(shù)，除了1和它自身外，不能整除其他自然數(shù)的數(shù)叫做質(zhì)數(shù)冷守；否則稱為合數(shù)刀崖。
篩選法求質(zhì)數(shù)
- 用一個布爾數(shù)組isPrime表示某個范圍range內(nèi)的整數(shù)是否為質(zhì)數(shù)，如果下標(biāo)為k的數(shù)組元素的值為true拍摇，則表示
整數(shù)k是質(zhì)數(shù)亮钦；否則，不是質(zhì)數(shù)充活。因此蜂莉，初始時，isPrime[1]位false混卵，isPrime[2]為true映穗，數(shù)組中其他元素的值均為true. - 遍歷isPrime數(shù)組，下標(biāo)從1開始幕随，到range的開方結(jié)束蚁滋。根據(jù)“質(zhì)數(shù)的倍數(shù)不是質(zhì)數(shù)”的規(guī)則，改變isPrime數(shù)組的值赘淮。
遍歷結(jié)束后辕录，isPrime數(shù)組中下標(biāo)為非質(zhì)數(shù)的整數(shù)的元素值為false，而下標(biāo)為質(zhì)數(shù)的整數(shù)的元素值還是true梢卸。
畫一下重點啊走诞，質(zhì)數(shù)的倍數(shù)不是質(zhì)數(shù)
源碼如下
import java.util.Arrays;
public class PrimerNumber {
/**
* 用篩選法求質(zhì)數(shù)
* @param range
* @return
*/
private boolean[] sieve(int range){
if(range <=0){
System.out.println("求質(zhì)數(shù)的范圍range必須大于0！");
return null;
}
// 用一個布爾數(shù)組標(biāo)識是否為質(zhì)數(shù)蛤高，如果下標(biāo)為質(zhì)數(shù)
// 那么該下標(biāo)對應(yīng)的數(shù)組元素的值為true
// 比如2是質(zhì)數(shù)蚣旱，則isPrime[2] =true
// 因為數(shù)組下標(biāo)是從0開始的，所以這里新建的數(shù)組大小為range+1
boolean[] isPrime = new boolean[range+1];
isPrime[1] = false; //1不是質(zhì)數(shù)
//用Arrays的fill方法將數(shù)組下標(biāo)從2到range+1之間的元素的值都賦為true
Arrays.fill(isPrime,2,range+1,true);
int n = (int)Math.sqrt(range);
for(int i=1;i<=n;i++){
//如果i是質(zhì)數(shù)戴陡，那么i的倍數(shù)不是質(zhì)數(shù)
if(isPrime[i]){
for(int j=2*i;j<=range;j+=i){
isPrime[j] = false;
}
}
}
return isPrime;
}
/**
* 顯示range范圍內(nèi)的質(zhì)數(shù)
* @param range 范圍的上限
*/
public void showPrimerNumber(int range){
boolean[] primes = this.sieve(range);
int number = 0 ;
if(primes!=null){
int size = primes.length;
System.out.println("范圍在"+range+"內(nèi)的質(zhì)數(shù)有:");
for(int i=1;i<size;i++){
if(primes[i]){
System.out.print(i+" ");
//每輸出10個質(zhì)數(shù)換行
// number先加1塞绿，再跟10做摸運算,如果余數(shù)為0，則換行
if(++number % 10 ==0){
System.out.println();
}
}
}
System.out.println();
}
}
public static void main(String[] args){
int range = 200;
PrimerNumber test = new PrimerNumber();
test.showPrimerNumber(range);
}
}
