使用过滤器和生成器在 python 中生成无穷无尽的素数

Question

下面是我发现使用 Sieve of Eratosthenes 查找素数的 python 程序。它使用过滤器和生成器。我看不懂。

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

这不仅仅是单行行代码，而是那行代码重复运行，具有不同的 n.

值

基本上，it 是一个迭代器，它产生尚未被筛子排除的候选素数。您首先让所有奇数成为候选人。

it = _odd_iter()

然后你重复拿第一个剩下的候选人，

while True:
    n = next(it)

删除所有是该候选人的倍数的数字，

    filter(_not_divisible(n), it)

并用删除倍数后剩下的所有内容替换您的候选素数。

    it = ...

如果你假装 filter returns 一个数字列表而不是一个可迭代对象，并且假装 _odd_iter() returns 一个奇数列表而不是一个可迭代对象，您可以跟踪循环并确定每个点的列表中的内容。比如运行ning

后

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() returns 是一个迭代器，而不是一个列表，所以您最终会得到一个嵌套的迭代器序列。特别是，您从

开始

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 2

首先，过滤迭代器 returns 另一个迭代器。 IE。当我们做类似的事情时：

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

我们得到一个链式迭代器"odd number AND not divisible by 3 AND not divisible by 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)

...等等

Answer 3

对于找到的每个质数，将 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

使用过滤器和生成器在 python 中生成无穷无尽的素数

using filter and generator to generator endless prime number in python

python

algorithm

yield

generator