埃氏筛选法求素数 Python

代码如下

def _odd_iter():  # 构建奇数序列 从3开始
    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) # 埃氏筛选法,产生筛选后新的序列

list_yc = list()
for n in primes():
    if n == 17:
        list_yc.append(n)
        break
    list_yc.append(n)

print(list_yc)

输出如下

[2, 3, 5, 7, 11, 13, 17]

代码分析

我不明白代码对别人来说是怎样的难度，我仅说说我自己第一次看到这个代码产生的疑问

1. it = filter(_not_divisible(n), it) 这一行代码中，调用方法 _not_divisible 方法 时，内部的lambda: x: x % n > 0中 x 的值是多少
2. it 是一个 Iterator, 每次next时才会返回一个值(for语句里面是每一次循环都调用一次next), 那序列中的 9 是怎样被 3 筛选掉的呢?

第一个问题:

这个地方是一个闭包调用，_not_divisible 返回了一个函数，而那个函数作用于 Iterator 中的每一个元素, 即 x 的值是 Iterator 中的每一个值

第二个问题:

首先追踪 _not_divisible 方法执行的每一步
改写 _not_divisible 如下

def _not_divisible(n):
    def lam(x):
        if n == 3:
            print('_not_divisible, n == 3', x)
        elif n == 5:
            print('_not_divisible, n == 5', x)
        return x % n > 0
    return lam

输出如下

_not_divisible, n == 3 5
_not_divisible, n == 3 7
_not_divisible, n == 5 7
_not_divisible, n == 3 9
_not_divisible, n == 3 11
_not_divisible, n == 5 11
_not_divisible, n == 3 13
_not_divisible, n == 5 13
_not_divisible, n == 3 15
_not_divisible, n == 3 17
_not_divisible, n == 5 17

埃氏筛选法 可以明显的看到用3，5筛选序列时是交替进行的。
可以肯定的是，用3筛选的时候没有一次性筛选所有的数字(事实上也不可能，因为_odd_iter是无限序列)
在用数字5筛选的之前，又使用了3筛选。那就是意味着用 3 筛选的方法被挂起了，每当有新数字，该方法会被唤醒且调用。以此类推，每一个数字对应的筛选函数都保存起来了(因为它要作用于序列中的每一个数字)
嗯。。。以上想法仅仅是个人折腾代码，调试出来的猜测，尚未向python大神确认。

思绪来的快去的也快，偶尔在这里停留