/*1. trick1 is to use square root of n.
2. trick2 is not to use nonprime numbers as the step
3. trick3 is to use i*i as the start.
4. trick4 is to use count in every loop, avoiding another traversal. */
int countPrimes(int n) {
if(n <= 2) return 0;
if(n == 3) return 1;
bool *prime= (bool*)malloc(sizeof(bool)*n);
int i=0,j=0;
int count = n2;
int rt = sqrt(n);//trick1
for(j = 0; j < n; j++)
{
prime[j] = 1;
}
for(i = 2; i <= rt; i++)
{
if (prime[i])//trick2
{
for(j=i*i ; j<n ; j+=i)//trick3
{
if (prime[j])
{
prime[j]=0;
count;//trick4
}
}
}
}
free(prime);
return count;
}
My C solutions in 44ms, time nearly O(n), and space nearly O(n)



Nice solution! Java version:
public int countPrimes(int n){ if(n<=2) return 0; if(n==3) return 1; boolean [] isPrime = new boolean[n]; Arrays.fill(isPrime, true); int count=n2; int sqrt = (int)Math.sqrt(n);//trick1 for(int i=2;i<=sqrt;i++){ if(isPrime[i]){ //trick2 for(int j=i*i;j<n;j+=i){ //trick3 if(isPrime[j]){ //when j appears again, don't do count isPrime[j]=false; count; //trick4 } } } } return count; }

Nice answer, but not fast enough. Here is my answer, only 36ms.
int countPrimes(int n) { if (n<=2) return 0; bool *notPrime= (bool*)malloc(sizeof(bool)*n); memset(notPrime,false,n); int sum = 1; for (int i=3; i<n; i+=2) { if (!notPrime[i]) { sum++; if(i>sqrt(n)) continue; for (int j=i*i; j<n; j+=i) { notPrime[j] = true; } } } free(notPrime); return sum; }