Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
def sieve(limit):
# Start by generating a list of bools with all even indexes flagged as not prime
# This substitutes the index in a list for actual numbers with a boolean
# flag indicating primality instead of actually maintaining the int in memory
# (since bools are much cheaper)
start = [False if i % 2 == 0 else True for i in range(limit)]
# Make sure to set 0 and 1 as not prime
start[0] = start[1] = False
for (i, isprime) in enumerate(start):
# If it's prime, yield it and set its multiples to false, else move on
if isprime:
# this is the magic - the yield keyword turns this into a generator
# meaning that you can start iterating over the results of sieve()
# as they're generated
yield i
# xrange is like range but cheaper
for n in xrange(2*i, limit, i): # Mark factors non-prime
start[n] = False
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment