线性筛法，保证每个合数，一定会被且只会被最小质因子筛一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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();
    }
};