Prime generator in python

Question

I am writing a prime generator, which is different from anyone in this link

generator in Python generating prime numbers

Here is my code

def sequence():
    i = 1 
    while True:
        i += 2
        yield i

def prime_generator(n):
    i = 2
   it = sequence()
    while i < n:
        it= filter(lambda x: x % i, it)
        i = next(it)
        yield i

when i run something like

for i in prime_generator(50):
    print(i)

It never dump 15, 33, sth like that for me. In a word, It gives me 2 and all odd numbers. what goes wrong here?

Uhm, 15 isn't prime. Neither is 33. – Morgan Thrapp Dec 01 '15 at 14:49 — Morgan Thrapp, Dec 01 '15 at 14:49
On the other hand, all odd numbers show up. *Interesting*. – Karoly Horvath Dec 01 '15 at 14:49 — Karoly Horvath, Dec 01 '15 at 14:49

score 3 · Accepted Answer · answered Dec 01 '15 at 14:46

3

The problem is that i inside the lambda isn't "fixed"; when i changes in the outside scope, the previously created lambda functions all use the new value, and so they all do the same check: see if the current value from sequence() is divisible by the last found prime. Which they never are.

Wrapping it into another lambda and then calling it so that the value of i can be fixed works:

def prime_generator(n):
    i = 2
    it = sequence()
    while i < n:
        it = (lambda i: filter(lambda x: x % i, it))(i)
        i = next(it)
        yield i

Edit: also I don't believe your code (nor this) does yield 2, but that can be trivially fixed.

answered Dec 01 '15 at 14:46

RemcoGerlich

30,470
6
61
79

2

Rather than wrapping it in another lambda you could use a default argument: `it = filter(lambda x, i=i: x % i, it)` – PM 2Ring Dec 01 '15 at 15:01
Sure, but I prefer the default arg method rather than using a closure because it's more compact, it's flatter, and in my tests it tends to run a little faster. – PM 2Ring Dec 01 '15 at 15:28
The nice thing about the default argument solution is that it becomes a local variable in the function (I think), and they have super fast lookups, so that will definitely help. But it feels slightly wrong to me to have a default argument that will never be used as a real argument and it's only a stack overflow answer to a hobby question, so I'll stick to what looks cleanest to me :-) – RemcoGerlich Dec 01 '15 at 15:35

Prime generator in python

1 Answers1

Linked