小编典典

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

algorithm

以下是我发现的使用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,如何用单行代码排除它?


阅读 292

收藏
2020-07-28

共1个答案

小编典典

对于找到的每个素数,将a 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
2020-07-28