Erstellen eines einfachen Primzahlsiebs in Python

Question

Ich schrieb ein einfaches Primzahlsieb (ein unbegrenztes Sieb von Eratosthenes) mit Python, aber aus irgendeinem Grund funktioniert es nicht richtig. Hier ist das Sieb:

from itertools import count 

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

Leider funktioniert das nicht. Stattdessen gibt es nur die gleichen Werte zurück wie der count (2) Iterator.

Zum Vergleich dazu:

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)) 

gedruckt wird:

2 
3 
5 

während das Sieb Funktion gedruckt wird:

Ich dachte, das Thema war mit dem seltsamen Verhalten von Pythons Lambd ein, wobei jedoch diese Zeile:

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

mit:

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

das Problem nicht lösen.

Answer 1

Das Problem ist, dass die lambda immer auf den neuesten Wert von n, nicht derjenige verwendet, bezieht sich, wenn lambda erstellt wurde. Der einfachste Weg, um es ist, den Wert explizit mit einem Schlüsselwort-Argumente zu erfassen:

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 

Dieser Python Gotcha ist well-documented in variousanswers Stackoverflow. Um fair zu sein, wird das gleiche Verhalten auch von einigen anderen Sprachen mit lexikalischen Schließungen wie JavaScript und Common Lisp geteilt.

Es könnte sein, was Sie mit "seltsames Verhalten von Python Lambda" in der Frage gemeint, obwohl dieses Verhalten nichts mit lambda zu tun hat, aber mit was eine Schließung wirklich erfasst, wenn eine veränderbare Variable - in Python, JavaScript und Common Lisp erfasst den letzten Wert der Variablen, während in Scheme der Wert der Variablen erfasst wird, wie er zum Zeitpunkt der Erstellung der Schließung war.