```
class Solution {
public:
int countPrimes(int n) {
if(n < 3) return 0;
bool *a = new bool[n];
int end = int(sqrt(double(n))) + 1;
int ans = 0;
for(int i = 2; i < end; ++i){
if(!a[i]){
++ans;
for(int j = i<<1; j < n; j += i){
if(a[j]) continue;
a[j] = true;
}
}
}
for(int k = end; k < n; ++k){
if(!a[k]) ++ans;
}
delete [] a;
return ans;
}
};
```