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


  • 33
    S
        /*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;
    }

  • -1
    A
    This post is deleted!

  • 0
    C

    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.


  • 0
    A

    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.


  • 0
    Q

    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


  • 0
    W

  • 0
    S

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

  • 0
    K

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

Log in to reply
 

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