埃氏筛筛选整数,埃拉托斯特尼筛法简称埃氏筛,是一个筛选质数的算法。该算法用迭代的方式识别出已经找到的质数的倍数,能高效地筛选小于一千万的质数。让我们试着去寻找第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)