Accepte, C++ method.


  • 1

    refer: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

     int countPrimes(int n) 
        {
        	if (2 >= n)	return 0;
        	
        	bool* primes = new bool[n];
        	for (int i = 2; i < n; ++i)
        		primes[i] = true;
        
        	int sqr = sqrt(n - 1);
        	for (int i = 2; i <= sqr; ++i)
        	{
        		if (primes[i])
        		{
        			for (int j = i + i; j < n; j += i)
        				primes[j] = false;
        		}
        	}
        
        	int sum = 0;
        	for (int i = 2; i < n; ++i)
        		sum += (primes[i]) ? 1 : 0;
        
        	delete[] primes;
        
        	return sum;
        }

  • 0
    T

    for (int j = i + i; j < n; j += i)

    should be
    for (int j = i * i; j < n; j += i) ?


  • 0

    it is a great idea!!


  • 3
    J

    As the wiki said.

    int countPrimes(int n) 
    {
        if (2 >= n) return 0;
    
        bool* primes = new bool[n];
        for (int i = 2; i < n; ++i)
            primes[i] = true;
    
        int sqr = sqrt(n - 1);
        for (int i = 2; i <= sqr; ++i)
        {
            if (primes[i])
            {
                for (int j = i * i; j < n; j += i)
                    primes[j] = false;
            }
        }
    
        int sum = 0;
        for (int i = 2; i < n; ++i)
            sum += (primes[i]) ? 1 : 0;
    
        delete[] primes;
    
        return sum;
    }
    

    Not j=i+i It's j=i*i


  • 0

    you are right!!
    thanks


  • 0
    B

    You could count while iterating through the array. That could save some time:

    int sum = 0;
    for (int i = 2; i < n; ++i)
    {
    	if (primes[i])
    	{
    		sum++;
    		for (int j = i + i; j < n; j += i)
    			primes[j] = false;
    	}
    }

  • 0

    this will reduce the the amount of code.
    But i don't think it will save so many time.

    I think, no matter "in" or "out", the two methods will do O(n) "plus operate" .


  • 0
    B

    From order perspective, it's still O(n). But we could still saving something:
    (1) sqr "if (primes[i])" check operations. Originally the two iteration has some duplication.
    (2) "sum += (primes[i]) ? 1 : 0;" will have n "plus operation" (either add 1 or 0), while "if (primes[i]) sum++" will have less than n "plus operation" (only add 1).


  • 0

    yeas you are right


Log in to reply
 

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