素数算法

看到廖雪峰网站上用python的实现, 看起来很简单, 但是最终还是自己实现一遍比较好, ==代码点我跳转.==

• 素数算法 (埃拉托色尼筛选法)

原理很简单, 在数学界1既不是质数也不是合数, 所以不用管1, 从2开始

输出最小的质数`2`, 然后将`2`的倍数都删除
输出剩下的第一个数为`3`, 然后将`3`的倍数都删除
输出剩下的第一个数为`5`, 然后将`5`的倍数都删除
输出剩下的第一个数为`7`, 然后将`7`的倍数都删除
...

这样不断循环下去, 直到所有的数都被删除或者输出, 输出的数即为质数.

• 实现

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

这里先定义一个ori_iter方法, 返回的是一个生成器(从3开始的奇数, 如 3, 5, 7...)

def _not_divisible(n):
    return lambda x: x % n > 0

这里定义了一个_not_divisible方法, 这可以理解成一种规则, x能整除n返回false, 不能整除则返回true, 后面filter中有用到

def prime():
    it = _ori_iter()
    while True:
        n = next(it)
        yield n
        # it = filter(lambda x: x % n > 0, it)
        it = filter(_not_divisible(n), it)

这里定义的prime返回的则是全体素数. 第一行的it = _ori_iter(), 这时it是一个会返回从3开始的所有奇数(也就是不能被2整除)的生成器==(3, 5, 7, 9, 11...)==, while True表示将会无限循环下去,直到天荒地老, 下面是循环过程

1. 取出的第一个n是it的第一个元素3, yield n将3作为prime生成器的第一个元素. 之后经过it = filter(_not_divisible(n), it), 这里的it经过筛选, 将3的倍数全部丢弃==(3, 5, 7, 9, 11...)==
2. 取出被筛选过的it的第二个元素, 也就是5, 作为prime生成器的第二个元素. 之后在经过it = filter(_not_divisible(n), it)筛选, 将5的倍数全部丢弃(3, 5, 7, 11, 13, 15...)
3. 取出被筛选过的it的第三个元素, 也就是7, 作为prime生成器的第三个元素. 之后在经过it = filter(_not_divisible(n), it)筛选, 将7的倍数全部丢弃(3, 5, 7, 11, 13...21...)
4. ...

这是一个无限循环, 所以prime返回的是一个的生成器, 里面包含无穷多个质数

• 总结
  算法很容易理解, 实现起来也并不难, 下面是在实现的过程中遇到的一个问题

def _not_divisible(n):
    return lambda x: x % n > 0

def prime():
    it = _ori_iter()
    while True:
        n = next(it)
        yield n
        # it = filter(lambda x: x % n > 0, it)
        it = filter(_not_divisible(n), it)

最后两句分为注释部分it = filter(lambda x: x % n > 0, it)和未注释部分it = filter(_not_divisible(n), it)咋一看并没有什么区别, 但是输出的结果却大有不同, 这就有意思了, 思前想后, 请教同事, 最后总算是有点理解, 这里大致描述一下为什么会出现输出不同的情况...

生成器(Iterator)是一种惰性计算的序列(他很懒, 你催他一下, 他才会给你下一个数据- -), 只有当你使用next取值时, 才会去执行, 然后返回给你正确的值

• 这里如果使用未注释部分, it = filter(lambda x: x % n > 0, it)这里的n值确实是上一句正确返回的n值, 但是由于filter也是惰性的, filter只会去执行一次筛选, 然后到下次循环时, n的值就变了成下次返回的n, 这样每次filter都只会筛选一次, 真正需要筛选出去的值并没有被筛选, 最后的执行结果显然不会正确了...
• 然而使用未注释部分代码, n的值是通过_not_divisible函数的参数传进去的, 不会去改变, 传进去第一个3, 他就会一直筛选下去, 然后传进第二个5的时候, 同理也会筛选下去, 所以可以得出正确的质数序列

归根结底, 这里应该是filter和lambda内部处理的问题, 可能研究一下源码会更加明了, 这里就先不倒腾了/哭笑...