с использованием фильтра и генератора для бесконечного простого числа генераторов в python

Question

Ниже приведена программа python, которую я нашел, чтобы найти простые числа, используя Sieve of Eratosthenes. Он использует фильтр и генератор. Я не могу это понять.

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 

То, что я не понимаю, это it = filter(_not_divisible(n), it). Например, для номера 105, как он исключается этой отдельной строкой кода?

Answer 1

Для каждого простого числа Найденного filter применяется к итерации, фильтр используется является которая исключает все кратные простого числа.

Таким образом, ваш итерабельный обернут столько фильтров, сколько вы нашли простые числа, например, число 105 исключено, поскольку оно делится на 3, а фильтр для всех кратных 3 был добавлен, когда вы нашли простое число 3.

Если добавить некоторые print заявления будет немного понятнее (я надеюсь):

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 

который печатает:

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

Не только это одиночный строка кода, это то, что линия выполняется многократно, с различными значениями n.

В принципе, it - это итератор, который дает простые простые числа кандидатов, которые еще не были исключены ситом. Вы начинаете с того, что делаете все нечетные числа кандидатами.

it = _odd_iter() 

Тогда вы повторно взять первый оставшийся кандидат,

while True: 
    n = next(it) 

удалить все числа, кратные этого кандидата,

filter(_not_divisible(n), it) 

и заменить кандидатов простых чисел со всем, что осталось после удаления кратных.

it = ... 

Если вы претендуете filter возвращает список чисел, а не итератора, а также делать вид _odd_iter() возвращает список нечетных чисел вместо итератора, можно проследить через петлю и определить, что в списке на каждый пункт.Например, после запуска

it = _odd_iter() 

начать с

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

Затем запустите

n = next(it) # 3 

который вытягивает первый элемент с передней, оставив вас с

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

и запустить

it = filter(_not_divisible(3), it) 

отфильтровывает все кратные 3,

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

Затем вернитесь к началу цикла и тянуть новый первый номер с переднего

n = next(it) # 5 

оставляя

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

, а затем отфильтровать все кратные 5,

it = filter(_not_divisible(5), it) 

который дает

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

и так далее.

На практике, поскольку filter() возвращает итератор, а не список, вы завершаете получение вложенной последовательности итераторов. В частности, вы начинаете с

it = _odd_iter() 

затем после первой итерации цикла, то есть в основном

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

за исключением того, что 3 была взята из итератора, а затем, после второй итерации петля у вас есть

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

за исключением того, что 5 также были взяты из итератора, а затем

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

и так далее.

Answer 3

Во-первых, фильтр через итератор возвращает другой итератор. То есть когда мы делаем что-то вроде:

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

Мы получаем цепочечную итератор «нечетное число и не делится на 3 и не делится на 5». Он немного похож на прикованные декоратор, где мы получаем эквивалент:

# 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) 

... и так далее