204. Count Primes

朴素eratosthenes筛数法
O(nloglogsqrt(n)) time
证明

class Solution {
public:
    int countPrimes(int n) {
        if (n < 2) return 0;
        vector<bool> isPrime(n, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i < n; ++i) {
            if (!isPrime[i]) continue; // 如果不是质数直接跳过
            for (int j = i * i; j < n; j += i) { // 要从i * i开始，因为i * 2到i * (i - 1)都已经筛过了
                isPrime[j] = false;
            }
        }
        return count(isPrime.begin(), isPrime.end(), true);
        // return count_if(isPrime.begin(), isPrime.end(), [](bool isPrime) { return isPrime; });
    }
};