Java求質(zhì)數(shù)的幾種常用算法分析

更新時間：2018年12月29日 10:38:58 作者：Wonder

這篇文章主要介紹了Java求質(zhì)數(shù)的幾種常用算法,結(jié)合實例形式分析了三種比較常見的求質(zhì)數(shù)算法原理及相關(guān)實現(xiàn)技巧,需要的朋友可以參考下

本文實例講述了Java求質(zhì)數(shù)的幾種常用算法。分享給大家供大家參考，具體如下：

1、根據(jù)質(zhì)數(shù)的定義求

質(zhì)數(shù)定義：只能被1或者自身整除的自然數(shù)（不包括1），稱為質(zhì)數(shù)。

利用它的定義可以循環(huán)判斷該數(shù)除以比它小的每個自然數(shù)（大于1），如果有能被它整除的，則它就不是質(zhì)數(shù)。

對應(yīng)代碼是：

void printPrime(int n){//判斷n是否是質(zhì)數(shù)
  boolean isPrime=true;//是否是質(zhì)數(shù)的標(biāo)志
  for(int i=n-1;i>1;i—){//n除以每個比n小比1大的自然數(shù)
   if(n%i==0){//如果有能被整除的，則不是質(zhì)數(shù)
    isPrime=false;
   }
  }
  if(isPrime){//如果是質(zhì)數(shù)，則打印出來
   System.out.print(n+" ");
   primeNumber++;//記錄質(zhì)數(shù)的個數(shù)
   if(primeNumber%10==0)//輸出10個質(zhì)數(shù)后換行
    System.out.println();
  }
}

2、利用一個定理——如果一個數(shù)是合數(shù)，那么它的最小質(zhì)因數(shù)肯定小于等于他的平方根。例如：50，最小質(zhì)因數(shù)是2，2<50的開根號

再比如：15，最小質(zhì)因數(shù)是3，3<15的開根號

合數(shù)是與質(zhì)數(shù)相對應(yīng)的自然數(shù)。一個大于1的自然數(shù)如果它不是合數(shù)，則它是質(zhì)數(shù)。
上面的定理是說，如果一個數(shù)能被它的最小質(zhì)因數(shù)整除的話，那它肯定是合數(shù)，即不是質(zhì)數(shù)。所以判斷一個數(shù)是否是質(zhì)數(shù)，只需判斷它是否能被小于它開跟后后的所有數(shù)整除，這樣做的運算就會少了很多，因此效率也高了很多。

對應(yīng)代碼是：

void printPrime(int n){//判斷n是否是質(zhì)數(shù)
  boolean isPrime=true;//是否是質(zhì)數(shù)的標(biāo)志
  int s=(int)Math.sqrt(n);//對n開根號
  for(int i=s;i>1;i—){//n除以每個比n開根號小比1大的自然數(shù)
   if(n%i==0){//如果有能被整除的，則不是質(zhì)數(shù)
    isPrime=false;
   }
  }
  if(isPrime){//如果是質(zhì)數(shù)，則打印出來
   System.out.print(n+" ");
   primeNumber++;//記錄質(zhì)數(shù)的個數(shù)
   if(primeNumber%10==0)//輸出10個質(zhì)數(shù)后換行
    System.out.println();
  }
}

3、篩法求質(zhì)數(shù)，效率最高，但會比較浪費內(nèi)存

首先建立一個boolean類型的數(shù)組，用來存儲你要判斷某個范圍內(nèi)自然數(shù)中的質(zhì)數(shù)，例如，你要輸出小于200的質(zhì)數(shù)，你需要建立一個大小為201（建立201個存儲位置是為了讓數(shù)組位置與其大小相同）的boolean數(shù)組，初始化為true。

其次用第二種方法求的第一個質(zhì)數(shù)（在此是2），然后將是2的倍數(shù)的數(shù)全置為false（2除外），即2、4、6、8……位置上置為false。然后是3的倍數(shù)的全置為false（3除外），一直到14（14是200的開平方），這樣的話把不是質(zhì)數(shù)的位置上置為false了，剩下的全是質(zhì)數(shù)了，挑著是true的打印出來就行了。

對應(yīng)代碼是：

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);//對range開根號
  for(int i=2;i<=n;i++)//注意需要小于等于n
   if(isPrime[i])//查看是不是已經(jīng)置false過了
    for(int j=i;j*i<range;j++)//將是i倍數(shù)的位置置為false
     isPrime[j*i]=false;
  return isPrime;//返回一個boolean數(shù)組
}

PS：這里再為大家推薦一款功能相似的在線工具供大家參考：

在線分解質(zhì)因數(shù)計算器工具：
http://tools.jb51.net/jisuanqi/factor_calc

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對大家java程序設(shè)計有所幫助。

您可能感興趣的文章: