题目描述

寻找小于 n 的最小质数的个数

方法与证明

基本的思路是以已知的质数排除未知的合数

一个合数一定可以被它的最小质因子标记

那么我们能不能按照顺序输出质数，每次知道一个质数，就尽最大可能排除合数。 用 cnt 记录发现的质数个数，考虑 n > 2 (n <= 2 结果是 0).

假设我们已经得到了最大的质数是 cp , A = {cp * k | k >= cp , 且 k < n } 这个集合都是合数

声明一个数组 vt， 标记所有当前已知的合数

那么如何得到下一个质数， 让 j = cp + 1 ; 直到 vt[j] = false && j < n

若存在， cp = vt[j], k = cp, cnt ++ , 重新计算 A 集合，标记 vt.

知道 j == n . 结束寻找，返回 cnt .

本问题的要点是，根据已知的连续质数，可以通过排除的方法能够得到下一个质数。
我们遍历的时候只需要拿当前最大质数p, 作为 > p 的合数的最小质因子排除即可。
每个质数作为最小质因子的时候，可以决定一个合数的集合。所以合数只被排除一次。
寻找质数的过程也是单调的，不回溯，因此复杂度也是 o(n)

还有一个问题就是，为什么下一个未被标记的数一定是质数？？
假如是合数m，那么m的最小质因子一定是 <= p， 然而 <= p 作为最小质因子所有合数我们都标记了，因此
m 也一定被标记了，与假设矛盾，因此 m 一定是质数。

C++ 代码

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) return 0; 
        vector<bool> st(n + 1);
        long long cp = 2,  k = cp, j = cp + 1, cnt = 1;
        while (true) {
          // 当前最大已知质数排除以它为最小质因子的合数 
           while (k * cp < n){
               st[k * cp] = true;
               k ++;
           }
          // 求出下一个质数
           while (st[j] && j < n) j++; 
          // 若存在，重复上述过程 
           if (j < n) {
              cp = j;
              k = cp; 
              j = cp + 1;
              cnt ++; 
           } else {
               break;
           }
        }
        return cnt;
    }
};