题目来源
Count the number of prime numbers less than a non-negative number, n.

计算小于n的整数里有多少个质数。我一开始想着直接算！如下：

class Solution {
public:
    int countPrimes(int n) {
        int res = 0;
        if (n == 1)
            return 0;
        for (int i=2; i<n; i++) {
            if (isPrimes(i))
                res++;
        }
        return res;
    }
    
    bool isPrimes(int x)
    {
        for (int i=2; i<=x/2; i++) {
            if (x % i == 0)
                return false;
        }
        return true;
    }
};

然后果然超时了…然后我也想不到别的方法了，只能看看讨论区。
设置一个大小为n的数组来标记i是否为质数，当遍历到n的时候，把所有n的倍数的数字都标记为非质数。

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> noPrime(n, false);
        int res = 0;
        if (n == 1)
            return 0;
        for (int i=2; i<n; i++) {
            if (noPrime[i-1] == false) {
                res++;
                for (int j=2; i*j<n; j++) {
                    noPrime[i*j-1] = true;
                }
            }
        }
        return res;
    }
};

然后可以有各种trick来减少运行时间，比如说除了2之外，只考虑奇数，如下：

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> noPrime(n, false);
        int res = 1;
        if (n <= 2)
            return 0;
        for (int i=3; i<n; i+=2) {
            if (noPrime[i-1] == false) {
                res++;
                for (int j=2; i*j<n; j++) {
                    noPrime[i*j-1] = true;
                }
            }
        }
        return res;
    }
};