python - 使用过滤器和生成器在 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

对于找到的每个素数，一个过滤器被应用于可迭代对象，所使用的过滤器是一个排除所有素数倍数的函数。

因此，您的可迭代对象包含在与您找到质数一样多的过滤器中，例如，数字 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