204. Count Primes

# Easy

要用一个特殊的方法来做会比较快。加速三部曲：

1. 遍历数组，判断每个数是不是素数

2. 遍历数组，判断每个数的时候，只除以[ 2, sqrt(n) ]区间的数看是否能整除即可

3. 建一个一样大小的数组isPrime[n]，初始化为true, 如果一个数是素数，则其倍数都是素数，直到遍历完所有数为止

C++

class Solution {
public:
    int countPrimes(int n) {
        if(n <= 2) return 0;
        
        int count = 0;
        vector<bool> isPrime(n, true);
        for(int i = 2; i < n; i ++) {
            if(!isPrime[i]){
                continue;
            }
            count ++;
            for(int j = 2; i*j < n; j ++) {
                isPrime[i*j] = false;
            }
        }
        return count;
    }
};

Hightlight initilize an array with length of a variable:

vector<bool> isPrime(n, true);

// wrong expression
// bool isPrime[n];