LeedCode 204. 計數質數

一、内容

給定整數 n ，傳回 所有小于非負整數 n 的質數的數量 。

 

示例 1：

輸入：n = 10
輸出：4
解釋：小于 10 的質數一共有 4 個, 它們是 2, 3, 5, 7 。

示例 2：

輸入：n = 0
輸出：0

示例 3：

輸入：n = 1
輸出：0

 

提示：

    0 <= n <= 5 * 106
           

二、思路

• 埃式篩法:一個數

  p

  p

  p若是一個合數，那麼必然可以被

  [

  2

  ，

  p

  −

  1

  ]

  [2，p - 1]

  [2，p−1]中的某個質數整除，那麼我們直接用前面的質數的倍數進行篩除便可以得到所有的質數。n個數中質數的個數大概為

  n

  /

  l

  o

  g

  n

  n/logn

  n/logn, 而需要枚舉的倍數次數為

  2

  /

  n

  ,

  3

  /

  n

  .

  .

  .

  .

  .

  n

  /

  n

  2/n, 3/n.....n/n

  2/n,3/n.....n/n是一個調和級數，當n趨于無窮時可以認為等于

  l

  o

  n

  n

  lonn

  lonn, 是以時間複雜度可以認為為

  O

  (

  n

  )

  O(n)

  O(n),但實際上是

  O

  (

  n

  l

  o

  g

  l

  o

  g

  n

  )

  O(nloglogn)

  O(nloglogn)

• 線性篩法: 每個合數隻被最小質因子篩一次，是以為

  O

  (

  n

  )

  O(n)

  O(n)。 我們用prime記錄所有的質數，然後每次枚舉質數來進行篩除，分為兩種情況。1.當i % prime[j] != 0時，代表prime[j]不是i的最小質因子，但是是i * prime[j]的最小質因子(因為是從小到大枚舉的質數)，篩除掉i * prime[j] 2.當i % prime[j] == 0時，prime[j]不僅是i的最小質因子，也是i * prime[j]的最小質因子，是以循環停止。因為後面的質數 * i 都會被最小質因子曬除，不用再重複篩。

三、代碼

• 埃式篩法

class Solution {
public:
    int countPrimes(int n) {
        int ans = 0;
        vector<bool> vis(n + 1, true); //判斷某個位置是否為質數，true代表是
        vis[0] = vis[1] = false;
        for (int i = 2; i < n; i++) {
            if (vis[i]) {
               for (int j = i + i; j <= n; j += i) { //隻是用質數來進行篩除
                   vis[j] = false;
               }    
            }
        }       
        for (int i = 2; i < n; i++)
            if (vis[i]) ans++;          
        return ans;                                                                                             
    }
};
           

• 線性篩法

class Solution {
public:
    int countPrimes(int n) {
        int ans = 0;
        vector<bool> vis(n + 1, true); //判斷某個位置是否為質數，true代表是
        vector<int> prime;
        for (int i = 2; i < n; i++) {
            if (vis[i]) prime.push_back(i); //是質數
            for (int j = 0; prime[j] <= n / i; j++) {
                vis[i * prime[j]] = false; //利用最小質因子進行篩除
                if (i % prime[j] == 0) break; //代表prime[j]是i的最小質因子，那麼後面的質數就不用再枚舉
            }
        }          
        return prime.size();                                                                                             
    }
};