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

  • 0

    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

    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:

    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
            '''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
            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
                    for p in D[q]: # move each witness to its next multiple
                    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.