204. Count Primes (Integer)

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

思路：寻找质数的方法

class Solution {
public:
    int countPrimes(int n) {
        int num = 0;
        if(n < 2) return num;
        
        int i, j, index;
        isPrime = new bool [n];
        isPrime[0]=false;
        isPrime[1]=false;
        for(i = 2; i < n; i++){
            isPrime[i] = true;//initialize as true, means all are primes
        }

        for(i = 2; i < n; i++){
            if(!isPrime[i]) continue;
            
            num++;
            for(j=2; i*j < n; j++){
                isPrime[i*j] = false;
            }
        } 

        return num;
    }
private:
   bool* isPrime; 
};