正文索引 [隐藏]

最近在精进Python，发现Python的语言特性使它能简洁优雅的描述埃筛求素数的过程，所以写篇博做个记录。

原理

更详细的内容可以参考我的这篇博文，这里只做一个简略的介绍。

筛法，顾名思义，用数去筛选。具体流程是这样的：

  1. 对于所有待选整数：2,3,4,5,6,7,8,9,10…..
  2. 选择第一个素数2，筛掉它所有的倍数得到：
    2,3,5,7,9,11,13,15…..
  3. 接着用下一个数3，根据步骤2可以知道这“下一个数一定是素数”，用它继续筛掉自己的倍数：
    2,3,5,7,11,13,17…..
  4. 重复这个步骤筛下去，剩下的就全是素数了

具体实现

完整代码

# 构造一个奇数生成器
def _odd_iter():
    n = 1
    while True:
        n += 2
        yield n

# 构造筛选器
def _not_divsible(n):
    return lambda x : x % n > 0

# 筛法素数生成器
def _find_prime():
    yield 2 # 返回第一个素数"2"
    it = _odd_iter()
    while True:
        n = next(it)
        yield n
        it = filter(_not_divsible(n), it) # 根据filter不断产生新的素数

for i in _find_prime():
    if i < 100:
        print(i)

分块介绍

奇数生成器

在Python中，有一种特殊的语法叫做生成器。在此前我们知道可以通过列表生成式

L = [x * x for x in range(1,100)]

来得到一个满足条件的数组，但这种方式得到的序列是有限且长度固定的，很多时候访问起来并不灵活，比如我需要数列中的(n, n+1, n+2)项。于是Python定义了生成器这种有意思的小玩意。

生成器就是针对这种整个序列能够通过特定算法推算出来的情况而定义的一种 一边循环一边计算的机制 ，它能够大量节省空间并简化代码。

上述生成式只需要稍加修改就能变成一个生成器：

g = (x * x for x in range(1,100))

对于一个函数，可以用yield关键字替代return，从而使整个函数变为一个更复杂的生成器，就像我们上文中定义的_odd_iter()一样：

def _odd_iter():
    n = 1
    while True:
        n += 2
        yield n

我们就可以使用它来方便地、连续不断地生成奇数了。而在埃筛中，这么做是因为所有的偶数都被第一个素数“2”筛掉了。在我们已知这个大前提的情况下，只去生成偶数会让整个流程变得更直观。

筛选器

# 构造筛选器
def _not_divsible(n):
    return lambda x : x % n > 0

lambda是Python中用来创建匿名函数的方法。它是一个拥有独立命名空间、函数体比传统def函数简洁很多的表达式。

不难读懂，_not_divsible()方法也是一个生成器，他会挑选(生成)出所有无法被n整除的数，也就是埃筛中“无法被筛去的数 ”。

函数主体

# 筛法素数生成器
def _find_prime():
    yield 2 # 返回第一个素数"2"
    it = _odd_iter()
    while True:
        n = next(it)
        yield n
        it = filter(_not_divsible(n), it) # 根据filter不断产生新的素数

首先返回第一个素数2，然后筛掉所有偶数，接着通过不断的循环去更新迭代器，让它能满足筛法原理中“不断筛掉合数”的条件。