Here are my 12 ms and 16ms with less space solutions

I saw there are submission within 10ms. Can anyone share that? Thanks!

12 ms:

Here notPrime[i] refer to the number a = 2* i + 1, so the marking process starts from a^2 which is 2i(i+1) back to index

```
int countPrimes(int n) {
if(--n < 2) return 0;
int m = (n + 1)/2, count = m, k, u = (sqrt(n) - 1)/2;
bool notPrime[m] = {0};
for(int i = 1; i <= u;i++)
if(!notPrime[i])
for(k = (i+ 1)*2*i; k < m;k += i*2 + 1)
if (!notPrime[k])
{
notPrime[k] = true;
count--;
}
return count;
}
```

16 ms with less space:

almost same as above just squeeze 8 bit into a char

```
int countPrimes(int n) {
if(--n < 2) return 0;
char notPrime[(n + 1)/16+1] = {0};
int count = (n+1)/2, k, u = (sqrt(n) - 1)/2;
for(int i = 1; i <= u;i++)
if(!(notPrime[i>>3] & (1<<(i&7))))
for(k = 2*i*(i + 1); k < (n + 1)/2;k += 2* i + 1)
if (!(notPrime[k>>3] & (1<<(k&7))))
{
notPrime[k>>3] |= (1<<(k&7));
count--;
}
return count;
}
```