Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

求出小于n的所有素数的个数 显然用埃氏素数筛选法

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

        return count;
    }
};