204. Count Primes

class Solution {
public:
    int countPrimes(int n) {
        if (n == 0) return 0;
        
        vector<bool> isPrime(n, true);
        isPrime[0] = isPrime[1] = false;
        for(int i=2;i<sqrt(n);++i) {
            if (isPrime[i]) {
				// 避免重复标记，从 i*i 开始
                for(int j=i*i;j<n;j+=i) {
                    isPrime[j] = false;
                }
            }
        }
        return count(isPrime.begin(), isPrime.end(), true);
    }
};