3

I am trying to write an infinite prime number generator based on the Sieve of Erastosthenes for learning purposes (I know it is not a real sieve and it is not efficient). The following code does not seem to work even though if I type very step in the interpreter it works correctly. Why is that?

import itertools

def gen_primes():
    integers = itertools.count(2)
    while True:
        i = integers.next()
        yield i
        integers = itertools.ifilter(lambda x: x % i != 0, integers)

The results returned are 2, 3, 4, 5, 6, etc. so it seems like the variable integers is not overwritten.

Here is an example in the interpreter of how it should work:

>> integers = itertools.count(2)
>> integers.next()
   2
>> integers = itertools.ifilter(lambda x: x % 2 != 0, integers)
>> integers.next()
   3
>> integers = itertools.ifilter(lambda x: x % 3 != 0, integers)
>> integers.next()
   5
>> integers = itertools.ifilter(lambda x: x % 5 != 0, integers)
>> integers.next()
   7
>> integers = itertools.ifilter(lambda x: x % 7 != 0, integers)
>> integers.next()
   11
Will Ness
  • 70,110
  • 9
  • 98
  • 181
user2944397
  • 91
  • 3
  • @user2357112: How is that a duplicate? The issue here is not lexical scoping or function argument evaluation, but repeated filtering of an iterator that's already advanced. – BrenBarn Aug 14 '16 at 09:26
  • 2
    @BrenBarn: No, the problem is that the `lambda` is looking up `i` at call time instead of definition time, so `i` is always `x - 1`. – user2357112 Aug 14 '16 at 09:28
  • @user2357112: I don't understand how i would always be x-1, could you elaborate in an answer? And how would you fix it? – user2944397 Aug 14 '16 at 09:41
  • Say `itertools.count` spits out a 5. What was the last value `i` was set to? That value was 4. – user2357112 Aug 14 '16 at 09:50
  • `(lambda x, i=i: x % i != 0, integers)` [solves your problem](http://ideone.com/mkuMWu). Otherwise, each `lambda` refers to the same `i` defined above it in the loop; and that `i`'s value is changing all the time. But you meant to store its value at the time when `lambda` gets created, and continue to use that same value. With the optional argument we create a new variable, also named `i`, which receives the value of the loop's `i` at the time the lambda gets created, and that new `i`'s value is now used in the lambda's body. – Will Ness Aug 15 '16 at 21:42

0 Answers0