using filter and generator to generator endless prime number in python

Question

Below is a python program I found to find prime numbers using Sieve of Eratosthenes. It uses filter and generator. I'm not able to understand it.

def _odd_iter():
    n = 1
    while True:
        n = n + 2
        yield n

def _not_divisible(n):
    return lambda x: x % n > 0

def primes():
    yield 2
    it = _odd_iter()
    while True:
        n = next(it)
        yield n
        it = filter(_not_divisible(n), it)

for n in primes():
    if n < 1000:
        print(n)
    else:
        break

What I don't understand is it = filter(_not_divisible(n), it). For example for number 105, how is it excluded by this single line of code?

Answer 1

For each prime number found a filter is applied to the iterable, the filter used is a function that excludes all multiples of the prime number.

So your iterable is wrapped in as many filters as you found prime numbers, for example the number 105 is excluded because it's divisible by 3 and the filter for all multiples of 3 was added when you found the prime number 3.

If you add some print statements it will be a bit clearer (I hope):

def _odd_iter():
    n = 1
    while True:
        n = n + 2
        yield n

def _not_divisible(n):
    print('add filter for all multiples of', n)
    return lambda x: print('check if', x, 'is divisible by', n, 'result: ', not (x % n > 0)) or x % n > 0

def primes():
    yield 2
    it = _odd_iter()
    while True:
        n = next(it)
        yield n
        it = filter(_not_divisible(n), it)

for n in primes():
    if n < 20:
        print(n)
    else:
        break

which prints:

2
3
add filter for all multiples of 3
check if 5 is divisible by 3 result:  False
5
add filter for all multiples of 5
check if 7 is divisible by 3 result:  False
check if 7 is divisible by 5 result:  False
7
add filter for all multiples of 7
check if 9 is divisible by 3 result:  True
check if 11 is divisible by 3 result:  False
check if 11 is divisible by 5 result:  False
check if 11 is divisible by 7 result:  False
11
add filter for all multiples of 11
check if 13 is divisible by 3 result:  False
check if 13 is divisible by 5 result:  False
check if 13 is divisible by 7 result:  False
check if 13 is divisible by 11 result:  False
13
add filter for all multiples of 13
check if 15 is divisible by 3 result:  True
check if 17 is divisible by 3 result:  False
check if 17 is divisible by 5 result:  False
check if 17 is divisible by 7 result:  False
check if 17 is divisible by 11 result:  False
check if 17 is divisible by 13 result:  False
17
add filter for all multiples of 17
check if 19 is divisible by 3 result:  False
check if 19 is divisible by 5 result:  False
check if 19 is divisible by 7 result:  False
check if 19 is divisible by 11 result:  False
check if 19 is divisible by 13 result:  False
check if 19 is divisible by 17 result:  False
19
add filter for all multiples of 19
check if 21 is divisible by 3 result:  True
check if 23 is divisible by 3 result:  False
check if 23 is divisible by 5 result:  False
check if 23 is divisible by 7 result:  False
check if 23 is divisible by 11 result:  False
check if 23 is divisible by 13 result:  False
check if 23 is divisible by 17 result:  False
check if 23 is divisible by 19 result:  False

Answer 2

First, filter over iterator returns another iterator. I.e. when we do something like:

it = filter(_not_divisible(3), it)
it = filter(_not_divisible(5), it)

We get a chained iterator "odd number AND not divisible by 3 AND not divisible by 5". It is somewhat similar to chained decorators, where we get an equivalent of:

# assuming we have decorator @not divisible
@not_divisible(2)
def iter():
    return xrange(inf)

# then, at every subsequent prime we do something like:
iter = not_divisible(3)(iter)
# next prime is 5:
iter = not_divisible(5)(iter)

... and so on

Answer 3

It's not just that single line of code, it's that line being run repeatedly, with different values of n.

Basically, it is an iterator that yields candidate prime numbers which have not yet been ruled out by the sieve. You start by making all odd numbers candidates.

it = _odd_iter()

Then you repeatedly take the first remaining candidate,

while True:
    n = next(it)

remove all numbers that are multiples of that candidate,

    filter(_not_divisible(n), it)

and replace your candidate primes with everything that is left after removing multiples.

    it = ...

If you pretend filter returns a list of numbers, rather than an iterable, and also pretend _odd_iter() returns a list of odd numbers instead of an iterable, you can trace through the loop and determine what's in the list at each point. For example, after running

it = _odd_iter()

you start with

it = 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, ...

Then run

    n = next(it) # 3

which pulls the first item off the front, leaving you with

it = 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, ...

and run

    it = filter(_not_divisible(3), it)

filter out all the multiples of 3,

it = 5, 7, 11, 13, 17, 19, 23, 25, ...

Then go back to the top of the loop and pull the new first number off the front

    n = next(it) # 5

leaving

it = 7, 11, 13, 17, 19, 23, 25, ...

and then filter out all the multiples of 5,

    it = filter(_not_divisible(5), it)

which gives

it = 7, 11, 13, 17, 19, 23, ...

and so on.

In practice, because filter() returns an iterator, not a list, you wind up getting a nested sequence of iterators. In particular, you start with

it = _odd_iter()

then after the first iteration of the loop, you have basically

it = filter(_non_divisible(3), _odd_iter())

except that 3 has been taken from the iterator, and then after the second iteration of the loop you have

it = filter(_non_divisible(5), filter(_non_divisible(3), _odd_iter()))

except that 5 has also been taken from the iterator, and then

it = filter(_non_divisible(7), filter(_non_divisible(5), filter(_non_divisible(3), _odd_iter())))

and so on.