埃拉托斯特尼筛法算法问题（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的，我明白筛法是怎么工作的。但是这个实现的具体方式让我有点困惑。感觉写这个页面的人挺聪明的。

我明白它是在遍历列表，找出质数，然后把质数的倍数标记为非质数。

但是这行代码到底是干什么的呢：

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

我搞明白了，它是从2*i开始切片到列表的末尾，步长为i，这意味着所有i的倍数，从2*i开始，然后是3*i，再到4*i，直到遍历完整个列表。

但是[None] * (n//i - 1)是什么意思呢？为什么不直接设为False呢？

谢谢。这是个比较具体的问题，应该有一个明确的答案，但我觉得在这里问比较合适。我会很感激能有个清晰的解释。

Answer 1

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

这只是一个简洁的写法

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

它的工作原理是给这个列表的一部分赋值为一堆None。

Answer 2

L * N 这个表达式会创建并连接 N 个 L 的“浅拷贝”，也就是说，它会复制 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) 的意思。