SieveOfEratosthenes

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