erastosthenes.py

from itertools import count

def sieve():
    """
    The Sieve of Erastosthenes.

    If you wanted to speed this up, your best bets are to throw in a wheel.
    The heapq module's already written in C, so that's as fast as it's going
    to get, though if you can think of a way to avoid quite so many calls to
    heapq.heapreplace() (or prevent if from sifting the heap prematurely for
    us), that'd help.
    """
    yield 2
    q = [(4, 2)]
    for i in count(3):
        composite, prime = q[0]
        if composite == i:
            while composite == i:
                heapq.heapreplace(q, (composite + prime, prime))
                composite, prime = q[0]
        else:
            heapq.heappush(q, (i * i, i))
            yield i