1
2
3

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

1
2

输入：n = 0
输出：0

1
2

输入：n = 1
输出：0

 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
26
27
28

class Solution {
public:
    /*
    ## 解题思路
    * 筛法
    1.[4...n]中，
      依次筛掉: 2的倍数2*i
               3的倍数3*i
            .. sqrt[n]的倍数j*i
    2. 剩下的数都是素数；
    */
    int countPrimes(int n) {
        if (n<2) {
            return 0;
        }
        vector<bool> isPrime(n, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for(int i=0; i<sqrt(n); ++i) {
            if(isPrime[i]) {
                for(int j=i*i; j<n; j+=i) {
                    isPrime[j] = false;
                }
            }
        }
        return count(isPrime.begin(), isPrime.end(), true);
    }
};