time complexity: `O(n * long(log(n)))`

```
int countPrimes(int n) {
vector<int> prime(n, 1);
int res = max(0, n - 2);
for (int i = 2; i < n; ++i) {
if (prime[i] == 1) {
for (int j = i + i; j < n; j += i) {
res -= prime[j];
prime[j] = 0;
}
}
}
return res;
}
```