埃拉托塞尼斯筛(见 http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)是一种过滤质数的算法。它通过迭代找出已发现素数的倍数。根据定义,这些倍数不是素数,可以剔除。

对于小于 1000 万的素数,这种筛法是有效的。现在让我们试着找出第 10001 个素数。

操作分为两步,让我们来看看如何操作。

第一个必经步骤是创建一个自然数列表:

首先, 我们先创建一个连续整数列表。为此,NumPy 提供了 ( arange ) 方法:

NumPy基础之埃拉托塞尼斯筛

第二步: 筛选出 ( p ) 的倍数。

我们不确定这是否是埃拉托斯特尼想要我们做的,但它确实有效。在下面的代码中,我们传递了一个 NumPy 数组,并去掉了所有除以 ( p ) 后余数为零的元素:

NumPy基础之埃拉托塞尼斯筛

下面是这个问题的全部代码:

NumPy基础之埃拉托塞尼斯筛