class Solution {
public:
    int countPrimes(int n) {
        if (n == 0) return 0;
        vector<bool> flag(n, false);
        vector<int> p(n, 0);
        int index = 0;
        flag[0] = true, flag[1] = true;
        for (int i = 2; i <= n; i++) {
            if (!flag[i]) p[index++] = i;
            for (int j = 0; i * p[j] <= n; j++) {
                flag[i*p[j]] = true;
                if (i % p[j] == 0) break;
            }
        }
        return count(flag.begin(), flag.end(), false);
    }
};

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