Numpy 埃氏筛筛选整数|极客教程

埃氏筛筛选整数，埃拉托斯特尼筛法简称埃氏筛，是一个筛选质数的算法。该算法用迭代的方式识别出已经找到的质数的倍数，能高效地筛选小于一千万的质数。让我们试着去寻找第10 001个质数。

具体步骤

首先必须要做的事情，就是创建一个自然数列表。

创建一个连续的整数列表。

使用NumPy中的arange函数创建数组。

a = numpy.arange(i, i + LIM, 2)

筛选出p的倍数。

不清楚埃拉托斯特尼本人是否希望我们这样实现算法，但确实可以这样做。把数组中能被p整除的元素移除，代码如下。

a = a[a % p != 0]

本章的完整代码如下:

import numpy

LIM = 10 ** 6
N = 10 ** 9
P = 10001
primes = []
p = 2

#通过列出前6个质数: 2、3、5、7、11和13，我们看到第6个质数是13。
#第10 001个质数是多少？

def check_primes(a, p):
    #2. 筛选出p的倍数
    a = a[a % p != 0]

    return a
for i in xrange(3, N, LIM):
    #1. 创建一个连续的整数列表
    a = numpy.arange(i, i + LIM, 2)

    while len(primes)