Lazy Sieve of Eratosthenes in Python

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:
        pri开发者_开发问答me = 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.

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)

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

Here is a Python implementation of the genuine prime sieve based on the haskell code in the paper: The Genuine Sieve of Eratosthenes by Melissa E. O'Neill

It does not use recursion or trial division but is rather memory hungry.

from heapq import heappush, heappop, heapreplace
def sieve():
    w = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
    for p in [2,3,5,7]: yield p
    n,o = 11,0
    t = []
    l = len(w)
    p = n
    heappush(t, (p*p,n,o,p))
    yield p
    while True:
        n,o = n+w[o],(o+1)%l
        p = n
        if not t[0][0] <= p:
            heappush(t, (p*p,n,o,p))
            yield p
            continue
        while t[0][0] <= p:
            _,b,c,d = t[0]
            heapreplace(t, (b*d,b+w[c],(c+1)%l,d))

The following:

import itertools
print list(itertools.islice(sieve(),0,10))

prints:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]