我正在寻找一种生成质数的算法。我发现了 Robert William Hanks 制作的下面这个算法。它非常高效,比其他算法要好,但是我无法理解其中的数学原理。
def primes(n):
""" Returns a list of primes < n """
lis = [True] * n
for i in range(3,int(n**0.5)+1,2):
if lis[i]:
lis[i*i::2*i]=[False]*int((n-i*i-1)/(2*i)+1)
return [2] + [i for i in range(3,n,2) if lis[i]]
数组中的“True”值和最终的质数数组之间有什么关系?
n < 2
,算法将失败。 - Brian J Murray//
比使用浮点数除法并转换结果更高效。也就是说,lis[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
。 - PM 2Ring