# Fastest solution in C(20ms), using Bit Manipulation, less space !!!

• #define M 5000000
char z[8] = { 1, 2, 4, 8, 16, 32, 64, 128 };
char e[M/8];
int countPrimes(int n) {
int i,k,m,c;
c = n>=3;
n>>=1;
for (i = 1; i < n; i++)
if (!(e[i >> 3] & z[i & 7]) && ++c)
for (k = (i << 1) + 1, m = i + k; m < n; e[m >> 3] |= z[m & 7], m += k);
return c;
}

• Shifting on the fly instead of using z seems to consistently improve it from 24ms to 20ms.

• Really? I tried it before, but it is also 24ms.....

• Yes, I tried each multiple times.

Just to be sure we're talking about the same:

#define M 5000000
char e[M/8];
int countPrimes(int n) {
int i,k,m,c;
c = n>=3;
n>>=1;
for (i = 1; i < n; i++)
if (!(e[i >> 3] & (1 << (i & 7))) && ++c)
for (k = (i << 1) + 1, m = i + k; m < n; e[m >> 3] |= (1 << (m & 7)), m += k);
return c;
}

• yes, the same code.I tried it serveral times just now and got some 20ms and 24ms. you are right. :-D

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