Creating a simple prime sieve in Python

Question

I wrote a simple prime sieve (an unbounded sieve of Eratosthenes) using Python, but for some reason, it isn't working correctly. Here is the sieve:

from itertools import count

def sieve():
    nums = count(2)
    while True:
        n = next(nums)
        nums = filter(lambda k: k%n != 0, nums)
        yield n

Unfortunately, this isn't working. Instead, it just returns the same values as the count(2) iterator would.

For comparison, this:

nums = count(2)
print(next(nums))
nums = filter(lambda k: k%2 != 0, nums)
print(next(nums))
nums = filter(lambda k: k%2 != 0, nums)
print(next(nums))

will print:

2
3
5

while the sieve function will print:

2 3 4

I thought the issue was with the weird behavior of Python's lambda, but replacing this line:

nums = filter(lambda k: k%n != 0, nums)

with:

def f(k): return k%n != 0
nums = filter(f, nums)

doesn't solve the issue.

[That is not a Sieve of Eratosthenes.](https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf) — Veedrac, Mar 12 '15 at 06:01

score 8 · Accepted Answer · edited May 23 '17 at 12:06

The problem is that the lambda is always referring to the latest value of n, not the one used when lambda was created. The simplest way around it is to capture the value explicitly using a keyword argument:

from itertools import count

def sieve():
    nums = count(2)
    while True:
        n = next(nums)
        nums = filter(lambda k, n=n: k%n != 0, nums)
        yield n

This Python gotcha is well-documented in various StackOverflow answers. To be fair, the same behavior is also shared by some other languages with lexical closures, such as JavaScript and Common Lisp.

It might be what you meant by "weird behavior of Python lambda" in the question, although this behavior has nothing to do with lambda, but with what a closure really captures when referring to a mutable variable — in Python, JavaScript and Common Lisp it captures the latest value of the variable, while in Scheme it captures the value of the variable as it was at the time the closure was created.

I think this answer is great, however I had to use `ifilter` rather than `filter` to get it to work. Is that expected? With `filter`, it seems to hang. I'm on python 2.7,which might be relevant. A primes generator fuction is a really neat idea. — J Richard Snape, Mar 11 '15 at 23:03
@JRichardSnape Yeah, the OP is using Python 3, where `filter` is lazy and equivalent to `itertools.ifilter` in Python 2. The Python 2 `filter` is eager and quickly spends all available memory trying to build an infinite list. — user4815162342, Mar 12 '15 at 07:30

Creating a simple prime sieve in Python

1 Answers1