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

• 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:

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
``````

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