class Solution {
public:
    int countPrimes(int n) {
        int *tmp = new int[n];
        memset(tmp,0,sizeof(int)*n);
        int count = 0;
        for(int i = 2; i < n ; i++){
            if(tmp[i] == 0){
                count ++;
            for(int j = 2; j*i < n; j++)
                tmp[i*j]=1;
            }
        }
        return count;
    }
};