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 commented Dec 5, 2017

@sfaleron

This comment has been minimized.

Copy link
Owner Author

sfaleron commented Jul 30, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.