我正在寻找生成素数的算法。我发现以下由罗伯特·威廉·汉克斯(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]]
Trues值数组和最终质数数组之间有什么关系?
True
与开始 Ñ True值阵列,i从枚举3到sqrt(n)通过的步骤2,如果 我 在阵列中个条目仍然True,从设定的所有条目i^2通过的步骤阵列的端部2*i到False(这些将是倍数i)。
i
3
sqrt(n)
2
i^2
2*i
False
True最后留在数组中的所有奇数条目都是素数。
这样找到的所有数字1和 2 都是存在于 n 以下的质数。