Skip to content

Instantly share code, notes, and snippets.

@sfaleron

sfaleron/lazyprimes_py3.py

Last active Jul 30, 2019
Embed
What would you like to do?
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[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)))
@sfaleron

This comment has been minimized.

Copy link
Owner Author

@sfaleron sfaleron commented Dec 5, 2017

@sfaleron

This comment has been minimized.

Copy link
Owner Author

@sfaleron sfaleron commented Jul 30, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment