# My C solutions in 44ms, time nearly O(n), and space nearly O(n)

• ``````    /*1. trick1 is to use square root of n.
2.  trick2 is not to use non-prime 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 = n-2;
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;
}``````

• This post is deleted!

• Thank you. Very interesting method. Instead of division by subtraction to avoid wasting time. After the all products are excluded from the total, the rest are prime numbers.

• This is an interesting method, and could you please tell me how did you come up with this idea? What is the thoughts behind this? Thank you.

• thanks for your trick 4, really brilliant!

with the help of several current posts, I find it could be further optimized. ignore the even numbers will be more efficient. below is my post,

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

• 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=n-2;
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;
}``````

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