小编典典

质数发生器解释?

algorithm

我正在寻找生成素数的算法。我发现以下由罗伯特·威廉·汉克斯(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值数组和最终质数数组之间有什么关系?


阅读 437

收藏
2020-07-28

共1个答案

小编典典

与开始 Ñ True值阵列,i从枚举3sqrt(n)通过的步骤2,如果
在阵列中个条目仍然True,从设定的所有条目i^2通过的步骤阵列的端部2*iFalse(这些将是倍数i)。

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

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

2020-07-28