I was trying to solve a coding problem in C++ which counts the number of prime numbers less than a non-negative number `n`

.

So I first came up with some code:

```
int countPrimes(int n) {
vector<bool> flag(n+1,1);
for(int i =2;i<n;i++)
{
if(flag[i]==1)
for(long j=i;i*j<n;j++)
flag[i*j]=0;
}
int result=0;
for(int i =2;i<n;i++)
result+=flag[i];
return result;
}
```

which takes 88 ms and uses 8.6 MB of memory. Then I changed my code into:

```
int countPrimes(int n) {
// vector<bool> flag(n+1,1);
bool flag[n+1] ;
fill(flag,flag+n+1,true);
for(int i =2;i<n;i++)
{
if(flag[i]==1)
for(long j=i;i*j<n;j++)
flag[i*j]=0;
}
int result=0;
for(int i =2;i<n;i++)
result+=flag[i];
return result;
}
```

which takes 28 ms and 9.9 MB. I don't really understand why there is such a performance gap in both the running time and memory consumption. I have read relative questions like this one and that one but I am still confused.

EDIT: I reduced the running time to 40 ms with 11.5 MB of memory after replacing `vector<bool>`

with `vector<char>`

.

`vector<bool>`

is special. – Jesper Juhl Apr 18 at 11:45`for(int i = 2; i * i <n;i++)`

since if`i * i >= n`

then next loop does nothing. – Marek R Apr 18 at 12:20`true`

and`false`

and not`1`

. So:`vector<bool> flag(n+1, true);`

and`if (flag[i])`

. That doesn't affect the result, but it makes it much clearer what you're doing. – Pete Becker Apr 18 at 12:53enabledbefore benchmarking. – Jesper Juhl Apr 18 at 14:22