Wordzilla - 1 year ago 32

Python Question

I am trying the following to generate the prime numbers till a given limit. I thought of using sieve of eratosthenes. When I use a list I get the correct output but when I don't make it as a list the output is false and gives back all numbers. Is there a way to do this with recursion and since there is a recursion limit imposed in python is there any other way to use the below structure. I read through Rosetta code to check for implementations that use a set and also with a list where they set the number as not prime with a dictionary.

`def prime_till(number):`

seq = range(2, number)

while True:

try:

first = seq.__next__()

except AttributeError:

first = seq.__iter__().__next__()

except StopIteration:

return None

yield first

seq = list(filter(lambda x: x % first != 0, seq))

print(list(prime_till(20)))

Output :

`[2, 3, 5, 7, 11, 13, 17, 19]`

Without list :

`def prime_till(number):`

seq = range(2, number)

while True:

try:

first = seq.__next__()

except AttributeError:

first = seq.__iter__().__next__()

except StopIteration:

return None

yield first

seq = filter(lambda x: x % first != 0, seq)

print(list(prime_till(20)))

Output :

`[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]`

Answer Source

I'm not a python expert, but I've done some debugging on your code. It seems, that the lambda expression is evaluated at the time the sequence is read. That is, in the actual expression `x % first`

the `first`

is substituted every time with the **current** value of `first`

, not the one that was at the time you created the filter.

Here's some weird code to prove it:

```
def prime_till(number):
seq = iter(range(2, number))
while True:
try:
first = next(seq)
print(first)
except StopIteration:
return None
if first == 2:
seq = filter(lambda x: x % 2 != 0, seq)
elif first == 3:
seq = filter(lambda x: x % 3 != 0, seq)
elif first == 5:
seq = filter(lambda x: x % 5 != 0, seq)
else:
seq = filter(lambda x: x % first != 0, seq)
if first == 5:
print(list(seq))
prime_till(20)
```

Result:

```
2
3
5
[7, 11, 13, 17, 19]
```

Here's another answer on the same topic: Deferred evaluation in python

Now, as for how to fix this issue, I have honestly no idea, but I'm looking into it.

**Added:**
I've constructed some working code using the idea described by @schlamar in that other question I've linked.

```
from functools import partial
def modnotnull(denom, value):
return value%denom != 0
def prime_till(number):
seq = iter(range(2, number))
while True:
try:
first = next(seq)
except StopIteration:
return None
yield first
seq = filter(partial(modnotnull,first), seq)
#Or a one-liner:
#seq = filter(partial(lambda denom,value: value%denom != 0,first), seq)
print(list(prime_till(20)))
```

Output:

```
[2, 3, 5, 7, 11, 13, 17, 19]
```

Explanation:

First I define a `modnotnull`

function, which performs the required check on given value and denominator. Then, each time the `first`

value is drawn, I create a new function out of it using the `partial`

function from `functools`

. Basically, I'm dynamically creating different lambdas the way I've shown in my first example. `partial(modnotnull,2)`

becomes `lambda value: value % 2 != 0`

and so on. Effectively, this forces python to evaluate one of my arguments at the time the filter is created.