LeetCode204，计算质数，线性筛

题目

素数筛选，线性筛。

求1 - n之间的素数个数，不包含n。

题解

思路

若$x=a\ast b,a\ne 1,b\ne 1$, 那么$x$是合数
一个合数$x$，可以写成 $x=p_1\ast p_2\ast ...\ast p_i\ast ...\ast p_n$, pi是x的质数，设$p^{\prime }=min(P)=p_i$,
$x=p^{\prime }\ast p[1:i-1]\ast p[i+1:n]$
设，$q=p[1:i-1]\ast p[i+1:n]$
则，$x=p^{\prime }\ast q$
对于一个确定的$x$，$p^{\prime }/q$都是确定的，也就是说$x=p^{\prime }\ast q$有唯一的表示，那么当我枚举到$q$ (第一个循环)的时候，我再枚举它的倍数（素数倍，第二个循环），枚举到$p^{\prime }$倍，也就能得到$x=p^{\prime }\ast q$, 而且只有在$q$的时候，我才会枚举得到$x$，也就是说，$x$只会在第二个循环出现一次，可得时间复杂度是O(n)。

对于任意的合数x，$x=p^{\prime }\ast q,q<x$那么$q$一定会被枚举到，$p^{\prime }$是$x$最小的质因数，那么$p^{\prime }$也一定会被枚举到，那么$x$也一定会被枚举到，即能枚举到所有的合数。

时间复杂度

O(n)

空间复杂度

O(n) 标记素数，暂存素数

代码

/*

*/
class Solution {
public:
    int countPrimes(int n) {
        vector<int> prim;
        vector<int> flag(n);
        if(n > 1) flag[1] = 1;
        for(int i = 2; i < n; i++) {
            if(flag[i] == 0) prim.push_back(i);
            for(int j = 0; j < prim.size() && i * prim[j] < n; j++) {
                flag[prim[j] * i] = 1;
                // i % prim[j] == 0, prim[j]是最小的x的最小苏因素
                // x = prim[j+1] * i, 因为prim[j]是i的素因素，
                //所以prim[j]是x的素因素，
                //所以prim[j+1]不是x的最小素因数，
                //所以x 会被其它数枚举得到，
                //可以计算得i' = x / prim[j]
                if(i % prim[j] == 0) break;
            }
        }
        return prim.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25