# Why I get TLE by using "vector<bool>"??? But "bool *" didn't??? And how about "vector<int>"???

1. vector<bool>
======

int countPrimes(int n)
{
vector<bool> prime(n + 1, true);

`````` int sqrn = sqrt(n);
for(int i = 2; i <= sqrn; ++ i)
if(prime[i])
for(int j = i * i; j < n; j += i)
prime[j] = false;

int res = 0;
for(int i = 2; i < n; ++ i)
if(prime[i])
++ res;
return res;
``````

}

And I got "Time Limit Exceeded"

1. bool *
======

I changed "vector<bool>" to "bool *" and used new to alloc memory.

I got "Accept".

``````int countPrimes(int n)
{
bool *prime = new bool[n];
for(int i = 0; i < n; ++ i)
prime[i] = true;

int sqrn = sqrt(n);
for(int i = 2; i <= sqrn; ++ i)
if(prime[i])
for(int j = i * i; j < n; j += i)
prime[j] = false;

int res = 0;
for(int i = 2; i < n; ++ i)
if(prime[i])
++ res;

delete[] prime;

return res;
}
``````

And the question is: new operation is fast than alloc of vector???

1. vector<int>
======

I used "vector<int>" and bit manipulation. Maybe It can save some time.

``````int countPrimes(int n)
{
int bit_num = sizeof(int) * 8;
vector<int> prime(n / bit_num + 1, -1);

int sqrn = sqrt(n);
for(int i = 2; i <= sqrn; ++ i)
if(prime[i / bit_num] & (1 << i % bit_num))
for(int j = i * i; j < n; j += i)
prime[j / bit_num] &= ~(1 << j % bit_num);

int res = 0;
for(int i = 2; i < n; ++ i)
if(prime[i / bit_num] & (1 << i % bit_num))
++ res;
return res;
}
``````

Also I got "Accept".

1. vector<int> and hammingWeight
======

I also used "vector<int>" and bit manipulation. And I got the number of 1 in each number by hammingWeight.

``````int countPrimes(int n)
{
int bit_num = sizeof(int) * 8;
vector<int> prime(n / bit_num + 1, -1);
prime[0] &= ~3;

int sqrn = sqrt(n);
for(int i = 2; i <= sqrn; ++ i)
if(prime[i / bit_num] & (1 << i % bit_num))
for(int j = i * i; j < n; j += i)
prime[j / bit_num] &= ~(1 << j % bit_num);

int res = 0;
for(int i = 0; i < prime.size() - 1; ++ i)
res += hammingWeight(prime[i]);
for(int i = n / bit_num * bit_num; i < n; ++ i)
if(prime[i / bit_num] & (1 << i % bit_num))
++ res;
return res;
}
int hammingWeight(int n)
{
int res = 0;
while(n)
{
++ res;
n &= n - 1;
}
return res;
}
``````

Also I got "Accept", and it fast than the upper one.

• Hi @makuiyu, your first solution is accepted for me. Maybe the server was incorrectly giving you TLE previously....

``````class Solution{
public:
int countPrimes(int n)
{
vector<bool> prime(n+1, true);

int sqrn = sqrt(n);
for(int i = 2; i <= sqrn; ++ i)
if(prime[i])
for(int j = i * i; j < n; j += i)
prime[j] = false;

int res = 0;
for(int i = 2; i < n; ++ i)
if(prime[i])
++ res;
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.