題目：寫一個程序判斷一個數(shù)是否是素?cái)?shù)。

• 直接利用定義敲代碼：

  boolean isprime(int n) {
       for(int i=2; i<n; ++i) {
           if(n%i==0)return false;
       }
       return true;
   }
  

• 對正整數(shù)n，如果用2到sqrt(n)之間的所有整數(shù)去除，均無法整除，則n為質(zhì)數(shù)。顯然for循環(huán)還可以繼續(xù)優(yōu)化：

     boolean isprime(int n) {
          for(int i=2; i*i<=n; ++i) {
              if(n%i==0)return false;
          }
          return true;
      }
  

  ?

現(xiàn)在我們換個提法：求1-100內(nèi)的素?cái)?shù)。

• 思路同樣簡單，只是加個for循環(huán)：

       for (int i = 2; i < 100; i++) {
                  if(isprime(i))
                      System.out.print(i+" ");
              }
  

• 但如果求1-10000內(nèi)（甚至是更高）的素?cái)?shù)，那么運(yùn)行起來就太慢了，如何解決？我想也許我們可以多花些空間來代替時間，也就是說先將素?cái)?shù)創(chuàng)造出來；我們知道2是素?cái)?shù)，但2的倍數(shù)就不是，如4、6等，同樣的道理可以推廣到所有素?cái)?shù)，那么我們就可以先將素?cái)?shù)的倍數(shù)設(shè)為0，那么遍歷完后，剩余的 !0數(shù)就是素?cái)?shù)了。

       void creat_prime(int value,int a[]) {  //value代表當(dāng)前素?cái)?shù)，調(diào)用時初始為2
              //排除2,3等素?cái)?shù)的倍數(shù)，剩余的非0就是素?cái)?shù)
              for (int i =2; i * value < n; i++) {
                  a[i * value]=0;
              }
              for (int i =value+1; i < n; i++) {
                      if(a[i]!=0) {
                          value=a[i];
                          creat_prime(value, a);
                          break;
                      }
                  }
              }           
  

  第一個for循環(huán)先排除2的倍數(shù)，第二個for循環(huán)是尋找下一個最小的素?cái)?shù)（在這里就是3），然后遞歸函數(shù)，直至將1-n內(nèi)的數(shù)全部遍歷。

• 運(yùn)行后會發(fā)現(xiàn)個問題，太多次的遞歸調(diào)用會導(dǎo)致內(nèi)存溢出

（java.lang.StackOverflowError），真是讓人頭疼，仔細(xì)觀察，是我想復(fù)雜了，其實(shí)只需兩層for循環(huán)就可以代替上面的遞歸調(diào)用，而且效率更高，代碼也更簡潔：

     //先初始化boolean []isPrime為true（此處省略），將非素?cái)?shù)改為false
     for (int i = 2; i * i < n; i++) {
           if (!isPrime[i]) continue;     //跳過非素?cái)?shù)
           for (int j = i * i; j < n; j += i) {
              isPrime[j] = false;
           }
        }

題目：Count Primes

Description:
Count the number of prime numbers less than a non-negative number, n.
https://leetcode.com/problems/count-primes/#/description

該題就是素?cái)?shù)優(yōu)化的應(yīng)用了，跟上面的最優(yōu)化代碼完全一致。

  public int countPrimes(int n) {
  boolean []isPrime =new boolean[n];
  for (int i = 2; i < n; ++i) {
    isPrime[i]=true;
  }

  //排除2,3等素?cái)?shù)的倍數(shù)，剩余的true就是素?cái)?shù)
  for (int i = 2; i * i < n; i++) {
        if (!isPrime[i]) continue;
        for (int j = i * i; j < n; j += i) {
          isPrime[j] = false;
        }
     }

  int count=0;
      for(int i=2;i<n;++i){
          if(isPrime[i])
              count++;
      }
  return count;
}

相關(guān)：

  <a >求前n個質(zhì)數(shù)的乘積</a>

  <a >分解質(zhì)因數(shù)</a>