Count the number of prime numbers less than a non-negative number, n. ``` Example: Input: 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7. ```

test.cpp

class Solution {
public:
    int countPrimes(int n) {
        if(n <= 2) return 0;
        vector<bool> passed(n,false);
        int sum = 1;
        int upper = sqrt(n);
        
        for(int i = 3;i < n;i += 2){
            if(!passed[i]){
                sum++;
                //avoid overflow
                if(i > upper) continue;
                for(int j = i * i;j < n;j += i){
                    passed[j] = true;
                }
            }
        }
        return sum;
    }
};