Similar idea with Sieve of Eratosthenes, but got TLE. Can someone help me here?


  • 0
    Y

    My solution is basically identical with Sieve of Eratosthenes.

    1. Initialize a list with [2, n).
    2. Get the head of list, which is the next prime number. Delete list head. Then iterate the list, delete all numbers which could be divided by the prime number.
    3. Repeat step 2 until the list is empty.

    Here is my code.

    class Solution {
    public:
        int countPrimes(int n) {
            if(n<=2)    return 0;
            int result = n-2;
            list<int> num;
            for(int i=2;i<n;i++){
                num.push_back(i);
            }
            result = 0;
            while(!num.empty()){
                int nextPrime = num.front();
                result++;
                num.pop_front();
                auto itr = num.begin();
                while(itr!=num.end()){
                    if((*itr) % nextPrime==0){
                        itr = num.erase(itr);
                    }else{
                        itr++;
                    }
                }
            }
            return result;
        }
    };

  • 0
    Y

    I think I figured it out myself. The inner loop iterates all numbers in the list to delete the numbers that could be divided by the prime number, which makes it inefficient. In the standard Sieve of Eratosthenes algorithm, it starts from i = prime*prime and increments i += prime each time.


Log in to reply
 

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