1.6 线性质数筛选

• 算法
• Python实现

  前面学过了埃拉托色尼筛选，也简称为埃氏筛。埃氏筛使用一个布尔数组来表示是否为质数，所以如果使用位集的话，可以大大节省存储空间。
  线性质数筛选，因为其算法复杂度为 O ( n ) O(n) O(n)，也就是复杂度是线性的，才得名线性质数筛选。线性质数筛选是Gries与Misra于1978年发明的，有时候也叫欧拉质数筛选，是因为欧拉更早使用了这种思想。
  线性质数筛选使用了一个最小质因数minimum prime factor数组。如果一个数的最小质因数是它自己，那么这个数字无疑是质数。如果最小质因数小于自己，那么这个数是个合数。
  我们处理每一个数时，都就将这个数乘以小于或等于自己的所有最小质因数，得到的这些数作为索引，把这个数设置为合数，并设置他们的最小质因数。如此循环下去，每次循环都只处理一个数字，所以复杂度是线性的。我举个例子：

  到了11，倍数就超过了20了，我就不再举例了。

# _*_ coding:utf-8 _*_

def sieve(n):
    mpfs = [0] * (n + 1)
    pn = []
    for i in range(2, n + 1):
        mpf = mpfs[i]
        if mpf == 0:
            pn.append(i)
            mpf = i
        for p in pn:
            if p > mpf:
                break
            x = p * i
            if x > n:
                break
            mpfs[x] = p
    return pn


if __name__ == '__main__':
    print(sieve(20))

  测试结果为：

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