It seems that all solutions I saw so far used O(n) space. So I came to share my slower (306ms) yet the less space-consuming solution (O(n/ln(n)). See the wiki page prime number theorem for why the space needed is O(n/ln(n)).

**Logic:** If a number is not a prime, then it can be divided by at least a prime. Thus, we maintain a vector of primes. Every time a number cannot be divided by the primes we know currently, we add it in.

```
class Solution {
public:
int countPrimes(int n) {
vector<int> primes;
for (int i = 2; i < n; ++i) {
bool isPrime = true;
int sqrt_i = sqrt(i);
for (int prime : primes) {
if (i % prime == 0) {
isPrime = false;
break;
} else if (prime > sqrt_i) {
break;
}
}
if (isPrime) {
primes.push_back(i);
}
}
return primes.size();
}
};
```

Any advice to improve the code would be appreciated. Many thanks.

TL