使用过滤器和生成器在python中生成无穷素数 [英] using filter and generator to generator endless prime number in python

问题描述

以下是我发现的Python程序，它使用蜘蛛网筛来查找素数。它使用过滤器和生成器。我无法理解。

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

我不明白的是 it = filter（_not_divisible（n），它）。例如，对于数字105，如何用单行代码排除它？

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?

推荐答案

对于找到的每个素数， filter 应用于迭代器，所使用的过滤器是一个功能，它排除素数的所有倍数。

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.

将iterable包裹在与您发现质数一样多的过滤器中，例如，排除了数字105，因为它可以被3整除，并且在找到质数3时添加了3的所有倍数的过滤器。

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.

如果添加一些 print 语句，它将更加清晰（我希望如此）：

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

哪些打印：

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

这篇关于使用过滤器和生成器在python中生成无穷素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！