题目描述

给定一个非负整数 $n$，统计共有多少个质数小于 $n$。

样例

输入：10
输出：4
解释：共有4个质数小于10，它们是 2, 3, 5, 7。

算法

(线性筛素数) $O(n)$

数论模板题，常用数论模板可以参考这里。

算法流程：

1. 从小到大枚举每个数 $i$；
2. 如果 $i$ 没有被标记，将 $i$ 加入质数集合；
3. 对于每个 $i$，从小到大枚举已有的质数 $prime_j$，将 $i * prime_j$ 标记成合数。如果 $i$ 能整除 $prime_j$，则直接break。

下面证明该算法是正确的，且时间复杂度是线性的：

首先，质数一定不是其它质数的倍数，所以质数一定会被找出来。然后我们证明，每个合数一定会被它的最小质因子标记，且只会被它的最小值因子标记，从而每个合数只会被标记一次，所以时间复杂度是线性的。

我们先来证明每个合数可以被它的最小质因子标记：
假设某个合数是 $x$，它的最小质因子是 $p$，令 $i = x / p$，则 $i$ 的所有质因子一定大于等于 $p$，所以当算法的第一层循环枚举到 $i$后，我们从小到大枚举质数时，$i$ 一定不能整除比 $p$ 小的质数，所以一定可以枚举到质数 $p$，从而可以把 $x = i * p$ 标记为合数。

然后我们证明每个合数仅会被它的最小质因子标记：
假设某个合数是 $x$，它的某个非最小的质因子是 $p$，令 $i = x / p$，则 $i$ 包含 $x$ 的最小质因子，从而 $i$ 存在某个质因子比 $p$ 小。所以当算法的第一层循环枚举到 $i$ 时，第二层循环枚举到 $i$ 的最小质因子后会直接break，不会枚举 $p$，所以 $x$ 一定不会被非最小的质因子标记。

证毕。

时间复杂度分析：每个合数仅会被它的最小质因子标记，所以每个合数只被标记1次，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    int countPrimes(int n) {
        vector<int> primes;
        vector<bool> st(n + 1);
        for (int i = 2; i < n; i ++ )
        {
            if (!st[i]) primes.push_back(i);
            for (int j = 0; i * primes[j] < n; j ++ )
            {
                st[i * primes[j]] = true;
                if (i % primes[j] == 0) break;
            }
        }
        return primes.size();
    }
};