# Simple 16 ms,10 line C++ solution. 1.use new bool array 2. only traverse odd numbers 3.count and sieve at the same time

1. use new bool array. 2. only traverse odd numbers. 3. count and sieve at the same time.

trick 1, thanks to 27ms,16 lines, C++ solution

trick 2, for the inspiration, thanks to my C solutions in 13ms,use Sieve of Eratosthenes and only test 6n-1 and 6n+1

``````int countPrimes(int n) {
if (n <= 2) return 0;
int res=n>>1, m=sqrt(n-1); // intilize res to n/2, removes all even number(not 2) and 1
bool *table=new bool[n];
for(int i=3,j,step;i<=m;i+=2)
if(!table[i]) { // i is an odd prime
for(step=i<<1, j=i*i;j<n;j+=step) // step=i*2, ignore even numbers
if(!table[j]) { table[j]=1; --res; }
}
delete []table;
return res;
}
``````

• Can you explain "sqrt(n-1)"? And I think "res = n >>1" because the algorithm skips even numbers, so the max numbers of prime will be n/2, can you confirm that please? Thanks!

• for sqrt part, in hint 3 of the problem desciption ([Count Primes][1]), "Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n."
[1]: https://leetcode.com/problems/count-primes/

• @qeatzy your array is not even initialized.

• Thank you for your share.
As @leo-lai-944 pointed out, your bool array is not initialized and you'll get Wrong Answer.
And what I want to say is that using unsigned char and bit manipulation can save much time and 7/8 space.
Here is a 9ms version:

``````class Solution {
public:
int countPrimes(int n)
{
if (n <= 2) return 0;
int ans = n >> 1, m = sqrt(n - 1); // intilize res to n/2, removes all even number(not 2) and 1
unsigned char *table = new unsigned char[n / 8 + 1];
memset(table, 0xff, n / 8 + 1);
for (int i = 3, j, step; i <= m; i += 2) {
if (table[i / 8] & (1 << (i % 8))) { // i is an odd prime
for (step = i * 2, j = i*i; j < n; j += step) { // step=i*2, ignore even numbers
if (table[j / 8] & (1 << (j % 8))) {
table[j / 8] ^= (1 << (j % 8)); // flip bit
--ans;
}
}
}
}
delete[] table;
return ans;
}
};
``````

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