Give a number N, it goes form 2 to n - 1, and remove all the multiples of N.

For example, when n is 8:

N=2: ** 2(×)**,3,

*4(×)*,5,

*6(×)*,7

N=3: ** 2(×)**,

**,**

*3(×)**4(×)*,5,

*6(×)*,7

N=4: ** 2(×)**,

**,**

*3(×)**4(×)*,5,

*6(×)*,7

N=5: ** 2(×)**,

**,**

*3(×)**4(×)*,

**,**

*5(×)**6(×)*,7

N=6: ** 2(×)**,

**,**

*3(×)**4(×)*,

**,**

*5(×)**6(×)*,7

N=7: ** 2(×)**,

**,**

*3(×)**4(×)*,

**,**

*5(×)**6(×)*,

*7(×)*```
class Solution {
public:
int countPrimes(int n) {
if (n < 2)
return 0;
std::vector<int> flag(n - 2, 1);
int res = 0;
for (int i = 0; i < n - 2; ++i)
if (flag[i]) {
++res;
for (int j = i; j < n - 2; j += i + 2)
flag[j] = 0;
}
return res;
}
};
```

Update:

```
class Solution {
public:
int countPrimes(int n) {
if (n <= 2)
return 0;
std::vector<int> flag(n, 1);
int res = 1, sqr = std::sqrt(static_cast<double>(n)), i = 3;
for (; i <= sqr; i += 2)
if (flag[i]) {
++res;
for (int j = i * i; j < n; j += i)
flag[j] = 0;
}
for (; i < n; i += 2)
res += flag[i];
return res;
}
};
```