Instantly share code, notes, and snippets.

# sfaleron/lazyprimes_py3.py Last active Jul 30, 2019

Infinite prime number generator for Python3
 # 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: 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 <= candidate: heapq.heapreplace(table, _Item(next(table), table)) 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)))
Owner Author

Owner Author

### sfaleron commented Jul 30, 2019

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