Skip to content

Instantly share code, notes, and snippets.

@Deathnerd
Last active September 30, 2015 20:28
Show Gist options
  • Save Deathnerd/a98500ed7c87f9c772d6 to your computer and use it in GitHub Desktop.
Save Deathnerd/a98500ed7c87f9c772d6 to your computer and use it in GitHub Desktop.
def primes():
"""
Generate an infinite series of primes based on the
Sieve of Eratosthenes
"""
D = {}
q = 2
while True:
if q not in D:
yield q
D[q*q] = [q] # Thank you Eratosthenes
else:
for p in D[q]:
# Back-fill the dictionary
# With keys being composites and the
# list value being its components
D.setdefault(p + q, []).append(p)
del D[q]
q += 1
primes_gen = primes() # instantiate the generator
print [next(primes_gen) for x in range(0,10)] # use it!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment