Sol. from ActiveState Recipes/Python Cookbook: Memory Limit Exceeded


  • 0
    S

    I was having a Memory Limit Exceeded problem with my solution (which was using the Sieve of Eratosthenes algorithm and a Python dictionary/hash table storing info about all the non-prime numbers) hence I've tested the Python coding recipe taken from the classic recipe site https://code.activestate.com/recipes/:
    https://code.activestate.com/recipes/117119-sieve-of-eratosthenes/

    The solution published in the famous book Python Cookbook (by Alex Martelli, Anna Ravenscroft, David Ascher) is based on the above one, hence is very similar:
    https://books.google.com/books?id=1Shx_VXS6ioC&pg=PT703

    Why do I still get the Memory Limit Exceeded error (still on the 20/20 test case, input: 1500000)? Now I'm not storing anymore the full hash table with all the non-prime numbers.

    class Solution(object):
        def countPrimes(self, n):
            """
            :type n: int
            :rtype: int
            """
            # Sieve of Eratosthenes
            # https://code.activestate.com/recipes/117119-sieve-of-eratosthenes/
            '''Yields the sequence of prime numbers via the Sieve of Eratosthenes.'''
            D = {}  # map composite integers to primes witnessing their compositeness
            q = 2   # first integer to test for primality
            primes_counter=0
            while q<n:
                if q not in D:
                    primes_counter+=1 # not marked composite, must be prime
                    D[q*q]=[q] # first multiple of q not already marked
                else:
                    for p in D[q]: # move each witness to its next multiple
                        D.setdefault(p+q,[]).append(p)
                    del D[q] # no longer need D[q], free memory
                q += 1
            return primes_counter
    

Log in to reply
 

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