Lazy Sieve of Eratosthenes in Python

Question

I am trying to code a lazy version of Sieve of Eratosthenes in Python 3.2. Here's the code:

import itertools
def primes():
    candidates = itertools.count(2)
    while True:
        prime = next(candidates)
        candidates = (i for i in candidates if i % prime)
        yield prime

However, when I iterate over primes(), I only get consecutive numbers. E.g.,

print(list(itertools.islice(primes(),0,10)))

prints the list

[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

To my surprise, the following tiny modification of primes() makes it work:

def primes():
    candidates = itertools.count(2)
    while True:
        prime = next(candidates)
        candidates = (i for i in candidates if i % prime)
        next(itertools.tee(candidates)[1]) ########### NEW LINE
        yield prime

I am guessing I am missing something about the scope of the parameters of the generator

candidates = (i for i in candidates if i % prime)

but I cannot see how to fix the code without adding this random-looking new line. Does anybody know what I am doing wrong? Thanks.

Answer 1

the fix is really to replace:

candidates = (i for i in candidates if i % prime)

with:

candidates = (lambda prime: (i for i in candidates if i % prime))(prime)

Answer 2

If you are worried about the scope of the variables, create objects/functions to keep these variables for you:

def filter_multiples(n, xs):
    for i in xs:
        if i % n
            yield i

def primes():
    candidates = itertools.count(2)
    while True:
        prime = next(candidates)
        candidates = filter_multiples(prime, candidates)
        yield prime

---

(I don't have access to a Pytho interpreter right now, so I don't konw if this actually works in the end or not...)

---

BTW, the algorithm you use is not really the sieve of Erastothenes. Take a look in this cool paper if you have some time: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf