#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;
}
Fastest solution in C(20ms), using Bit Manipulation, less space !!!

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; }