本文實(shí)例講述了java求質(zhì)數(shù)的幾種常用算法。分享給大家供大家參考，具體如下：
1、根據(jù)質(zhì)數(shù)的定義求
質(zhì)數(shù)定義：只能被1或者自身整除的自然數(shù)（不包括1），稱為質(zhì)數(shù)。
利用它的定義可以循環(huán)判斷該數(shù)除以比它小的每個(gè)自然數(shù)（大于1），如果有能被它整除的，則它就不是質(zhì)數(shù)。
對(duì)應(yīng)代碼是：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void printprime(int n){//判斷n是否是質(zhì)數(shù) boolean isprime=true;//是否是質(zhì)數(shù)的標(biāo)志 for(int i=n-1;i>1;i—){//n除以每個(gè)比n小比1大的自然數(shù) if(n%i==0){//如果有能被整除的，則不是質(zhì)數(shù) isprime=false; } } if(isprime){//如果是質(zhì)數(shù)，則打印出來(lái) system.out.print(n+" "); primenumber++;//記錄質(zhì)數(shù)的個(gè)數(shù) if(primenumber%10==0)//輸出10個(gè)質(zhì)數(shù)后換行 system.out.println(); }} |
2、利用一個(gè)定理——如果一個(gè)數(shù)是合數(shù)，那么它的最小質(zhì)因數(shù)肯定小于等于他的平方根。例如：50，最小質(zhì)因數(shù)是2，2<50的開(kāi)根號(hào)
再比如：15，最小質(zhì)因數(shù)是3，3<15的開(kāi)根號(hào)
合數(shù)是與質(zhì)數(shù)相對(duì)應(yīng)的自然數(shù)。一個(gè)大于1的自然數(shù)如果它不是合數(shù)，則它是質(zhì)數(shù)。
上面的定理是說(shuō)，如果一個(gè)數(shù)能被它的最小質(zhì)因數(shù)整除的話，那它肯定是合數(shù)，即不是質(zhì)數(shù)。所以判斷一個(gè)數(shù)是否是質(zhì)數(shù)，只需判斷它是否能被小于它開(kāi)跟后后的所有數(shù)整除，這樣做的運(yùn)算就會(huì)少了很多，因此效率也高了很多。
對(duì)應(yīng)代碼是：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void printprime(int n){//判斷n是否是質(zhì)數(shù) boolean isprime=true;//是否是質(zhì)數(shù)的標(biāo)志 int s=(int)math.sqrt(n);//對(duì)n開(kāi)根號(hào) for(int i=s;i>1;i—){//n除以每個(gè)比n開(kāi)根號(hào)小比1大的自然數(shù) if(n%i==0){//如果有能被整除的，則不是質(zhì)數(shù) isprime=false; } } if(isprime){//如果是質(zhì)數(shù)，則打印出來(lái) system.out.print(n+" "); primenumber++;//記錄質(zhì)數(shù)的個(gè)數(shù) if(primenumber%10==0)//輸出10個(gè)質(zhì)數(shù)后換行 system.out.println(); }} |
3、篩法求質(zhì)數(shù)，效率最高，但會(huì)比較浪費(fèi)內(nèi)存
首先建立一個(gè)boolean類型的數(shù)組，用來(lái)存儲(chǔ)你要判斷某個(gè)范圍內(nèi)自然數(shù)中的質(zhì)數(shù)，例如，你要輸出小于200的質(zhì)數(shù)，你需要建立一個(gè)大小為201（建立201個(gè)存儲(chǔ)位置是為了讓數(shù)組位置與其大小相同）的boolean數(shù)組，初始化為true。
其次用第二種方法求的第一個(gè)質(zhì)數(shù)（在此是2），然后將是2的倍數(shù)的數(shù)全置為false（2除外），即2、4、6、8……位置上置為false。然后是3的倍數(shù)的全置為false（3除外），一直到14（14是200的開(kāi)平方），這樣的話把不是質(zhì)數(shù)的位置上置為false了，剩下的全是質(zhì)數(shù)了，挑著是true的打印出來(lái)就行了。
對(duì)應(yīng)代碼是：
|
1
2
3
4
5
6
7
8
9
10
11
|
boolean[] printprime(int range){ boolean[] isprime=new boolean[range+1]; isprime[1]=false;//1不是質(zhì)數(shù) arrays.fill(isprime, 2,range+1,true);//全置為true（大于等于2的位置上） int n=(int)math.sqrt(range);//對(duì)range開(kāi)根號(hào) for(int i=2;i<=n;i++)//注意需要小于等于n if(isprime[i])//查看是不是已經(jīng)置false過(guò)了 for(int j=i;j*i<range;j++)//將是i倍數(shù)的位置置為false isprime[j*i]=false; return isprime;//返回一個(gè)boolean數(shù)組} |
希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。
原文鏈接：http://blog.sina.com.cn/s/blog_622e77cc0100n5lm.html
