埃氏筛筛选整数,埃拉托斯特尼筛法简称埃氏筛,是一个筛选质数的算法。该算法用迭代的方式识别出已经找到的质数的倍数,能高效地筛选小于一千万的质数。让我们试着去寻找第10 001个质数。
具体步骤
首先必须要做的事情,就是创建一个自然数列表。
- 创建一个连续的整数列表。
使用NumPy中的arange
函数创建数组。
- 筛选出
p
的倍数。
不清楚埃拉托斯特尼本人是否希望我们这样实现算法,但确实可以这样做。把数组中能被p
整除的元素移除,代码如下。
本章的完整代码如下:
埃氏筛筛选整数,埃拉托斯特尼筛法简称埃氏筛,是一个筛选质数的算法。该算法用迭代的方式识别出已经找到的质数的倍数,能高效地筛选小于一千万的质数。让我们试着去寻找第10 001个质数。
首先必须要做的事情,就是创建一个自然数列表。
使用NumPy中的arange
函数创建数组。
p
的倍数。不清楚埃拉托斯特尼本人是否希望我们这样实现算法,但确实可以这样做。把数组中能被p
整除的元素移除,代码如下。
本章的完整代码如下: