埃拉托色尼筛法问题（Python 语法）

Question

所以我正在阅读关于埃拉托斯特尼筛法的维基百科文章，其中包含一个 Python 实现： http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity_and_implementation

def eratosthenes_sieve(n):
    # Create a candidate list within which non-primes will be
    # marked as None; only candidates below sqrt(n) need be checked. 
    candidates = range(n+1)
    fin = int(n**0.5)

    # Loop over the candidates, marking out each multiple.
    for i in xrange(2, fin+1):
        if not candidates[i]:
            continue

        candidates[2*i::i] = [None] * (n//i - 1)

    # Filter out non-primes and return the list.
    return [i for i in candidates[2:] if i]

它看起来像非常简单和优雅的实现。我见过其他实现，甚至是 Python 中的实现，并且我了解 Sieve 的工作原理。但是这个实现的特定工作方式，我有点困惑。似乎编写该页面的人都非常聪明。

我知道它会迭代列表，找到素数，然后将多个素数标记为非素数。

但是这行代码到底做了什么：

candidates[2*i::i] = [None] * (n//i - 1)

我发现它从 2*i 到末尾切片候选，按 i 迭代，所以这意味着 i 的所有倍数，从 2*i 开始，然后转到 3*i，然后转到 4*i 直到完成列表。

n//i - 1) 是什么意思？为什么不将其设置为 False？

但是 [None] * ( 问题只有一个答案，但我认为这是问这个问题的地方，我肯定会感激一个清晰的解释。

Answer 1

candidates[2*i::i] = [None] * (n//i - 1)

只是一种简洁的编写方式

for j in range(2 * i, n, i):
    candidates[j] = None

，其工作原理是将一个 None 列表分配给一个 candidates 切片。

Answer 2

L * N 创建并连接 L 的 N（浅）副本，因此 [None] * (n//i - 1 ) 给出 ceil(n / i) 乘以 None 的列表。切片赋值 (L[start:end:step] = new_L) 会用 new_L 的项目覆盖切片接触的列表项目。

你是对的，人们也可以将这些项目设置为 False - 我认为这会更好，代码的作者显然认为 None 会更好地指示“划掉了”。但是 None 也可以工作，因为 bool(None) 是 False 和 .. if i 本质上是 if bool(i)< /代码>。