Python Forum - prime numbers with iterator and generator

Hello.

Let's make an iterator like this:

def integers_starting_from(n):
    while True:
        yield n
        n += 1

This makes an infinite sequence of integers.

for i in integers_starting_from(0):
    if i > 100:
        break
    else:
        print(i)

        
0
1
2
3
4
5
6
......

Next, let's make an iterator to produce prime numbers like this.

class Sieve(object):
    def __init__(self, stream):
        self.stream = stream
    def __iter__(self):
        return self
    def __next__(self):
        try:
            head = self.stream.__next__()
            self.stream = filter(lambda x: x % head != 0, self.stream)
            return head
        except StopIteration as e:
            raise e

Of course, this works too.

for prime in Sieve(integers_starting_from(2)):
    if prime > 100:
        break
    else:
        print(prime)

        
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

However the problem occurs here.
With the same logic stated above, let's try making a generator to produce prime numbers.
I wrote something like this:

def sieve(stream):
    while True:
        head = stream.__next__()
        yield head
        stream = filter(lambda x: x % head != 0, stream)

This does not work properly.
Did I make something wrong?

Thanx.

filter has a list of functions that it uses to test the iterable. You expected that list to look like this:

Output:lambda x: x % 2 != 0
lambda x: x % 3 != 0
lambda x: x % 5 != 0

And this is how the list looked in your iterator version.

In the generator version the list looked like this:

Output:lambda x: x % head != 0
lambda x: x % head != 0
lambda x: x % head != 0

All the functions are the same. You only test against the last prime number, not all known primes. And since the test is faulty, every number looks like a prime since "x % (x-1) != 0)" is True for all values of x > 2.

To fix the problem change this:

stream = filter(lambda x: x % head != 0, stream)

to this:

stream = filter(lambda x, y=head: x % y != 0, stream)

Note that integers_starting_from() already exists in the standard library, it is itertools.count().

Here is a less functionaly pure but nonetheless interesting sieve

from itertools import count
from functools import partial

def fil(s, x):
    if b := all(x % y for y in s):
        s.append(x)
    return b

def sieve():
    return filter(partial(fil, []), count(2))


if __name__ == '__main__':
    for x in sieve():
        print(x)
        if x > 100:
            break

(Dec-12-2022, 02:51 PM)deanhystad Wrote: [ -> ]filter has a list of functions that it uses to test the iterable. You expected that list to look like this:
Output:lambda x: x % 2 != 0
lambda x: x % 3 != 0
lambda x: x % 5 != 0
And this is how the list looked in your iterator version.

In the generator version the list looked like this:
Output:lambda x: x % head != 0
lambda x: x % head != 0
lambda x: x % head != 0
All the functions are the same. You only test against the last prime number, not all known primes. And since the test is faulty, every number looks like a prime since "x % (x-1) != 0)" is True for all values of x > 2.

To fix the problem change this:
stream = filter(lambda x: x % head != 0, stream)
to this:
stream = filter(lambda x, y=head: x % y != 0, stream)

O.K, thank you very much!
This seems a sort of pit fall; thus I would watch out when I use a generator.

(Dec-12-2022, 07:23 PM)Gribouillis Wrote: [ -> ]Note that integers_starting_from() already exists in the standard library, it is itertools.count().

Oops, I miss that one.
Thanx to notify me.

Quote:Here is a less functionaly pure but nonetheless interesting sieve

from itertools import count
from functools import partial

def fil(s, x):
    if b := all(x % y for y in s):
        s.append(x)
    return b

def sieve():
    return filter(partial(fil, []), count(2))


if __name__ == '__main__':
    for x in sieve():
        print(x)
        if x > 100:
            break

Interesting.
I'll check out the partial one, too.
Thank you!

(Dec-13-2022, 06:06 PM)cametan_001 Wrote: [ -> ]This seems a sort of pit fall; thus I would watch out when I use a generator.

When you do this:

stream = filter(lambda x: x % head != 0, stream)

Python creates a closure that contains the variable "head" and the anonymous function generated by the lambda expression.

def anoinymous(x):
    return x % head != 0

When the lambda expression is in your iterator, the variable "head" is different for each closure because each call to __next__(self) creates a new "head" variable.

When the lambda expression is in your generator, the variable "head" is the same for each closure because you never leave the generator scope.

You should probably use this notation for your iterator to prevent having to create a closure for each lambda.

stream = filter(lambda x, y=head: x % y != 0, stream)

This creates an anonymous function that kind of looks like this:

def anonymous(x, y=2):
    return x % y != 0

No need now for a closure because we don't use any variables, only function arguments.

(Dec-13-2022, 07:00 PM)deanhystad Wrote: [ -> ]
(Dec-13-2022, 06:06 PM)cametan_001 Wrote: [ -> ]This seems a sort of pit fall; thus I would watch out when I use a generator.
When you do this:
stream = filter(lambda x: x % head != 0, stream)
Python creates a closure that contains the variable "head" and the anonymous function generated by the lambda expression.
def anoinymous(x):
    return x % head != 0
When the lambda expression is in your iterator, the variable "head" is different for each closure because each call to __next__(self) creates a new "head" variable.

When the lambda expression is in your generator, the variable "head" is the same for each closure because you never leave the generator scope.

You should probably use this notation for your iterator to prevent having to create a closure for each lambda.
stream = filter(lambda x, y=head: x % y != 0, stream)
This creates an anonymous function that kind of looks like this:
def anonymous(x, y=2):
    return x % y != 0
No need now for a closure because we don't use any variables, only function arguments.

Thanks for the detailed explanation!
I tried some experiments like making a local function:

def anoinymous(x):
            nonlocal head
            return x % head != 0

, put it in the filter, and saw what is going on; however, as a result, what you showed is the only way to be succeess.

Anyway, thank you very much!

Or use a partial function. In a partial function the argument values are evaluated when the partial function is created, unlike a lambda expression where the argument values are evaluated when the expression is executed.

(Dec-15-2022, 04:29 PM)deanhystad Wrote: [ -> ]Or use a partial function. In a partial function the argument values are evaluated when the partial function is created, unlike a lambda expression where the argument values are evaluated when the expression is executed.

Hmm, like this.

def anoinymous(y, x):
    return x % y != 0

def sieve(stream):
    while True:
        head = stream.__next__()
        yield head
        stream = filter(partial(anoinymous, head), stream)

Yeah, it works.
Otherwise:

def sieve(stream):
    while True:
        head = stream.__next__()
        yield head
        stream = filter(partial(lambda y, x: x % y != 0, head), stream)

Interesting.
The order of arguments seems like functools.reduce, though.

Anyway, thanks!