What is wrong with these codes below ?


  • 0
    S

    Here is the first code:

    class Solution:
        # @param {integer} n
        # @return {integer}
        def countPrimes(self,n):
            self.n = n
        
            def is_prime(n):
                if n <2:
                    return False
                if n == 2:
                    return True
                for i in range(2,int(math.sqrt(n))):
                    if n%i == 0:
                        return False
                return True
                
            c = []
            for i in range(1,n,2):
                if is_prime(i):
                    c.append(i)
            return len(c)
    

    Alternatively, I am using the following implementation:

    def countPrimes( n):
            numbers = set(range(n,1,-1))
            primes = []
            while numbers:
                p = numbers.pop()
                primes.append(p)
                numbers.difference_update(set(range(2*p,n+1,p)))
            return primes
    

    In the first case, the error is : Time exceeds

    In the 2nd case, the error is : Memory exceeds

    But both runs fine on my laptop.

    Any explanation would be appreciated.

    Thanks


  • 0
    P

    Simply put, your first solution uses too much time while the second one uses too much space. We always need to try our best to optimize the code to pass the online judge.

    The first solution is a brute-force approach with a very high time complexity, and the second one re-claims a big set() in the while-loop for n times. Try to reuse existing result to avoid redundant computation or unnecessary space.


  • 1
    M

    This problem was designed to accept only optimized solutions.
    Hence the test case inputs are large numbers which exceeds time limits for codes which are below our "optimal threshold" - hence the time limit exceeded and memory exceeded errors.

    When you check if a number, let's say 53 is prime or not, this is what you have to do:
    check if 53 is DIVISIBLE by all PRIMES less than SQRT of 53.

    This is an optimized way of solving this problem.

    Feel free to reach out to me by replying to this post if you face any difficulties.


  • 0
    R

    Optimal solution using O(nlglgn) time and O(n) space exists. Search Eratosthenes for more


Log in to reply
 

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