//cpp:
class Solution {
public:
	int countPrimes(int n) {
		int count = 0;
		vector<bool> v(n);
		fill(v.begin(), v.end(), false);
		for (int i = 2; i < n; i++) {
			if (v[i])
				continue;
			count++;
			for (int j = i+i; j < n; j += i) {
				v[j] = true;
			}
		}
		return count;
	}
};