质数生成器解释？

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]]

Trues值数组和最终素数数组有什么关系？

Answer 1

从数组中的n True个值开始，i从3枚举到sqrt(n) 2，如果数组中第 i 个条目仍然是 True，则设置为 False 来自 [=18] 的所有条目=] 到数组末尾 2*i （这些都是 i 的倍数）。

最后留在数组中的 1 以上的所有奇数 True 项都是素数。

所有这样找到的数，和2，都是存在于n.

下方的所有素数

质数生成器解释？

Prime numbers generator explanation?

python

algorithm

math

primes

python-3.x