class Solution {
public:
    int countPrimes(int n) {
        vector<bool> pass(n,true);
        pass[0] = false, pass[1] = false;
        for(int i = 0; i<sqrt(n);++i)
        {
            if(pass[i])
            {
                for(int j = i*i; j<n; j+=i)
                {
                    pass[j] = false;
                }
            }
        }
        return count(pass.begin(),pass.end(),true);
    }
};

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;
}
};