Infinite prime number generator for Python3

lazyprimes_py3.py

# Originally from http://logn.org/2009/07/lazy-primes-sieve-in-python.html
# Updated for Python3 by Chris Fuller.

# The automated 2to3 translation doesn't work. The tricky bit is the heap item.
# This is a (int, object) tuple in the original module, but the second element
# becomes a map iterator in Python3, which does not compare, so an exception
# is raised when the heap is sorted.

# It turns out that the object in the original tuple is irrelevant to the sort
# (it compares by memory location, which isn't well defined!). The int deter-
# mines the comparison unless the ints are equal, and in this case either
# result is equivalent.

# The tuple heap item is replaced by a subclass of int, to clarify the sorting
# behavior. Instances of this subclass also support enough iteration to allow
# drop-in replacement.

class _Item(int):
    def __new__(cls, value, it):
        o = super().__new__(cls, value)
        o._it = it

        return o

    __next__ = lambda self: next(self._it)


# Author: Jared Brothers
#
# A Python version of the Haskell code from
# "The Genuine Sieve of Eratosthenes"
# www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
#

import heapq, itertools, operator
from functools import reduce

def sieve(xs):
    """Generate the prime numbers, given an iterable of candidate numbers.
    Cross off multiples of prime numbers incrementally using iterators."""
    table = []
    while True:
        candidate = next(xs)
        if table == [] or candidate < table[0]:
            yield candidate
            xs, ys = itertools.tee(xs)
            timesx = (lambda x: lambda y: x*y)(candidate)
            heapq.heappush(table, _Item(candidate**2, map(timesx, ys)))
        else:
            while table[0] <= candidate:
                heapq.heapreplace(table, _Item(next(table[0]), table[0]))

def wheel(factors=[2, 3, 5, 7], next=11):
    """Generate the distances between numbers not divisible by a list of small
    primes, from the next prime up to the product of the list."""
    circumference = reduce(operator.mul, factors)
    prev = next
    next += 1
    end = next + circumference
    while next < end:
        if not any(next % factor == 0 for factor in factors):
            yield next - prev
            prev = next
        next += 1

def spin(factors=[2, 3, 5, 7], next=11):
    """Generate candidates by making a wheel and cycling through it."""
    for gap in itertools.cycle(wheel(factors, next)):
        yield next
        next += gap

def primes(k=5):
    """Generate primes with the sieve and wheel factorization, which filters
    multiples of the first k primes."""
    smallprimes = list(itertools.islice(sieve(itertools.count(2)), k + 1))
    factors = smallprimes[:-1]
    next = smallprimes[-1]
    return itertools.chain(factors, sieve(spin(factors, next)))

Quick link to the original paper

Superseded by https://github.com/sfaleron/LazyPrimes