Creating a simple simple sieve in Python

Question

I wrote a simple right-handed sieve (unlimited Eratosthenes sieve) using Python, but for some reason it does not work correctly. Here is a 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 does not work. Instead, it simply returns the same values ​​as the count (2) iterator.

For comparison:

 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 problem was due to the strange behavior of Python 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) 

does not solve the problem.

Answer 1

The problem is that lambda always refers to the most recent value of n , and not to the one that was created when lambda was created. The easiest way is to explicitly commit the value using the 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 got well-documented answers in various StackOverflow. In fairness it follows that the same behavior is shared by other languages ​​with lexical closures, such as JavaScript and General Lisp .

This may be what you meant by the "strange Python lambda behavior" in the question, although this behavior has nothing to do with lambda , but with the fact that the closure really fixes when accessing a mutable variable - in Python, JavaScript and Common In Lisp, it captures the last value of a variable, whereas in Scheme it captures the value of a variable, as it was at the time the closure was created.