[python] good algorithm but Time Limit Exceeded at 1500000


  • 1
    S
    class Solution(object):
        def countPrimes(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n <= 2: return 0
            if n == 3: return 1
            # l is a list of discovered prime nums
            # prime nums other than 2 are all odd
            l = [3]
            
            
            # only test odd nums
            for i in range(3, n, 2):
                # i is prime if it doesn't have prime factors upto sqrt(i)
                # only test prime nums in l as factors
                bound = int(i ** 0.5)
                for j in l:
                    if i % j == 0:
                        break
                    if j > bound:
                        l.append(i)
                        break
                
            # 2 is not in list l, so add it on    
            return len(l) + 1
    

    I keep a list l to store discovered prime nums and test new number only on those in l and smaller than sqrt(i). I also explicitly skip even numbers larger than 2. This should be a better algorithm than that in hint, better than n ** 1.5. But it end up with Time Limit Exceeded. Any suggestions? Thanks.


  • 0
    J

    Er, you could use c++/java rather than python. Then you'll got an AC.

    I think the limit of runtime in Leetcode are 2000ms no mather which language you use. That means, with the same algorithm, python needs much much more time than c++/java/c/c#. So, you'll got a TLE in python while an AC in c++.

    // c++ version
    class Solution {
    public:
        int countPrimes(int n) {
            if (n <= 2)
                return 0;
            if (n == 3)
                return 1;
            
            vector<int> l;
            l.push_back(3);
            
            for (int i = 3; i < n; i += 2) {
                int bound = int(pow(i, 0.5));
                for (int j = 0; j < l.size(); j++) {
                    if (i % l[j] == 0)
                        break;
                    if (l[j] > bound) {
                        l.push_back(i);
                        break;
                    }
                }
            }
            return l.size() + 1;
        }
    };

  • 0
    S

    Thanks for your answer. I submitted with your code, which only beat 6% cpp codes. Since my algorithm is better (in terms of space) than one in the hint, there should be other reason I could not tell.


Log in to reply
 

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