My solution is basically identical with Sieve of Eratosthenes.

- Initialize a list with [2, n).
- Get the head of list, which is the next prime number. Delete list head. Then iterate the list, delete all numbers which could be divided by the prime number.
- Repeat step 2 until the list is empty.

Here is my code.

```
class Solution {
public:
int countPrimes(int n) {
if(n<=2) return 0;
int result = n-2;
list<int> num;
for(int i=2;i<n;i++){
num.push_back(i);
}
result = 0;
while(!num.empty()){
int nextPrime = num.front();
result++;
num.pop_front();
auto itr = num.begin();
while(itr!=num.end()){
if((*itr) % nextPrime==0){
itr = num.erase(itr);
}else{
itr++;
}
}
}
return result;
}
};
```