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