质数生成器的解释？

Question

我正在寻找一种生成质数的算法。我发现了 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”值和最终的质数数组之间有什么关系？

- Mu-Majid

---

看起来它正在使用埃拉托色尼筛法。 - ForceBru

该代码来自这个答案，基本上是稍微优化过的埃拉托斯特尼筛法。请注意，它是Python 2代码，需要进行一些调整才能在Python 3上使用。顺带一提，我在这个答案中有RWH代码的Python 3版本。 - PM 2Ring

请使用以下翻译：请以n = 6为例，逐步进行循环并在纸上写下lis和i的值。 - Peter Wood

建议的重复目标中没有一个答案完全复制了罗伯特·威廉·汉克斯的代码，尽管那里解释了一般原则。也许RWH本人会看到这个问题... - PM 2Ring

如果 n < 2，算法将失败。 - Brian J Murray

顺便说一下，使用//比使用浮点数除法并转换结果更高效。也就是说，lis[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)。 - PM 2Ring

Answer 1

从一个数组中以n个 True 值开始，使用步长为 2 的枚举变量 i（从 3 到 sqrt(n)），如果数组中第 i 项仍然是 True，则将从 i^2 到数组结尾的所有项（这些都是 i 的倍数）设置为 False，步长为 2*i。

在最后数组中剩下的所有奇数大于1的True条目都是素数。

所有发现的数字和2，都是小于n的所有素数。

- Will Ness