class Solution {
public:
    int countPrimes(int n) {
       vector<int> er(n), pr;
       int i, j, c = 0;
       for (i = 2; i < n; ++i)
       {
           if (!er[i])
           {
               er[i] = i;
               pr.push_back(i);
           }
           for (j = 0; j < pr.size() && pr[j] <= er[i] && pr[j] * i < n; ++j)
            er[pr[j] * i] = pr[j];
       }
       for (i = 2; i < n; ++i)
          if (er[i] == i)
            c++;
        return c;
    }
};