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.

note that `next(itertools.tee(candidates)[1])` can be rewritten as `next(candidates)` or in python 2 `candidates.next()`. — Dan D., Jul 16 '11 at 04:22
Could it be that `prime` is being bound only once rather than per loop iteration, meaning it doesn't remain constant per generator as expected? — Joey Adams, Jul 16 '11 at 04:26
Related: http://stackoverflow.com/questions/9043791/python-eratosthenes-sieve-algorithm-optimization — Dan D., Apr 20 '12 at 23:58

score 6 · Accepted Answer · answered Jul 16 '11 at 04:27

6

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)

answered Jul 16 '11 at 04:27

Dan D.

73,243
15
104
123

We don't usually see self-evaluating functions like that in Python :) – hugomg Jul 16 '11 at 04:32
the key issue is in `(i for i in x if i % p)`, `x` is bound once at the start but `p` is looked up for each item. – Dan D. Jul 16 '11 at 04:33
2

-1 Dude, that's plain wrong to build lambda functions that way. – Jul 16 '11 at 08:19
@Franklin I disagree. In highly mathematical routines where consiceness and efficiency are important, I believe heavy and even complex use of higher-order functions is justified. +1. – wberry Jul 16 '11 at 15:57
1

Ok... that works for me... if I only have to compute primes up to ~7900. After that, the sieve blows up with "RuntimeError: maximum recursion depth exceeded". Since I don't plan to recompile Python to change the recursion depth setting, I don't think this is a good method of computing primes for me... – Dan H Apr 20 '12 at 13:37
@DanH 1. You can use `sys.setrecursionlimit()` to increase the recursion depth setting as you call it without recompilation python. 2. In my other answer http://stackoverflow.com/a/10254923/388787 I have posted a Python implementation of the genuine sieve which does not use recursion nor trial division but it is rather memory hungry. – Dan D. Apr 20 '12 at 23:53

score 1 · Answer 2 · answered Apr 20 '12 at 23:49

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]

I'm sure this is correct (it works!) but I have absolutely no idea what any of it means. Please, at the very least, use more descriptive variable names! — Benjamin Hodgson, Oct 03 '12 at 23:12

score 1 · Answer 3 · answered Jul 16 '11 at 04:27

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

You might be interested in looking at an implementation of the genuine sieve in Python http://stackoverflow.com/a/10254923/388787 — Dan D., Apr 20 '12 at 23:54

Lazy Sieve of Eratosthenes in Python

3 Answers3