Add infinite prime generators

[Erotemic]

I've been thinking about prime numbers as I sometimes do. As I was looking a a sieve of Eratosthenes algorithm it caught my attention that it requires an upper limit on the maximum generated prime a-priori. It got me thinking of how I could implement a generator that would never stop generating primes (until the hardware gives out).

Next thing I know I'm on google and I stumble on this gem where several variants are given and discussed in detail:

https://stackoverflow.com/questions/2211990/how-to-implement-an-efficient-infinite-generator-of-prime-numbers-in-python/10733621#10733621

Specifically this algorithm:

def postponed_sieve():
    """
    Algorithm from Will Ness, Tim Peters, based on ActiveState code from David
    Eppstein, Alex Martelli, with ideas used by Guy Blelloch and likely others.
    """
    import itertools
    yield from (2, 3, 5, 7)
    # holds current multiples of each base prime (i.e. below the sqrt of the
    # current production point), together with their step values
    multiples = {}
    ps = postponed_sieve()
    next(ps)
    p = next(ps)
    psq = p * p
    for cand in itertools.count(9, 2):
        if cand in multiples:      # composite
            step = multiples.pop(cand)
        elif cand < psq:   # prime
            yield cand
            continue
        else:           # composite, = p*p
            step = 2 * p
            p = next(ps)
            psq = p * p
        cand += step
        while cand in multiples:
            cand += step
        multiples[cand] = step

[sylhare]

That's interesting, do you want to make a pull request to add it in?

[Erotemic]

Yeah, I can do that.