class Solution {
public:
    //const int maxn=100000;
    int countPrimes(int n) {
        bool* bprime  = new bool[n];
        memset(bprime,0,sizeof(bool)*n);
        for(int i=3;i<10000;i+=2)
        {
            if(!bprime[i])
                for(int j = i*i; j < n; j+=i<<1)
                    bprime[j] = 1;
        }
        int ans=1;
        if(n <3)
        ans=0;
        for(int i=3;i<n;i+=2)
            if(!bprime[i])
                ans++;
        delete [] bprime;
        return ans;
    }
};