质数发生器解释？

  • Z时代
  • 2024-01-10
  • 分类：问答

我正在寻找生成素数的算法。我发现以下由罗伯特·威廉·汉克斯（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值阵列，i从枚举3到sqrt(n)通过的步骤2，如果 我

在阵列中个条目仍然True，从设定的所有条目i^2通过的步骤阵列的端部2*i到False（这些将是倍数i）。

True最后留在数组中的所有奇数条目都是素数。

这样找到的所有数字1和 2 都是存在于 n 以下的质数。

以上是 质数发生器解释？ 的全部内容， 来源链接： utcz.com/qa/401425.html

回到顶部