Troublesome filter behavior when implementing the "Sieve of Eratosthenes" in python

Question

I came up with this Python code for the trial division variant of the "Sieve of Eratosthenes":

import itertools

def sieve():
    # begin with all natural numbers above 1
    picker = itertools.count(2)
    while True:
        # take the next available number
        v = next(picker)
        yield v
        # filter from the generator its multiples
        picker = filter(lambda x: x % v != 0, picker)

It doesn't work as I expected.

When debugging it I get some behavior I don't understand when filter gets called: the x parameter of the lambda gets a concrete argument which is the next element from the picker generator. I don't understand this behavior not even after looking at the documentation of filter.

Running

s = sieve()
for i in range(5):
    print(next(s))

I get:

2
3
4
5
6

Instead of

2
3
5
7
11

UPDATE:

My bug comes from a misunderstanding of how lambdas work in Python, more on that here.

Adding an extra parameter to the lambda fixes the issue:

picker = filter(lambda x, prime = v: x % prime != 0, picker)

Answer 1

I think the problem is because you rely on local variables and the generators you create (using filter()) are referencing the local variables which are overwritten when the generator goes on iterating.

If you use a local function instead, it works fine:

def sieve():
    def selector(iterator, d):
        for x in iterator:
            if x % d != 0:
                yield x
    picker = itertools.count(2)
    while True:
        # take the next available number
        prime = next(picker)
        yield prime
        # filter from the generator its multiples
        picker = selector(picker, prime)

Trying list(itertools.islice(sieve(), 10)) shows:

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

But I really need to point out that this is a purely educational solution to show how things work. I would not propose to use this solution for any productive code. It builds up a large amount of generators internally which are freed only when you drop the handle of the parent generator. This is probably a waste of resources and you can create an infinite amount of prime numbers without creating an infinite amount of generators.