python - 查看一个素筛程序，但不确定为什么它不断出现有关切片长度的错误

Question

def primes(n):
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]
    print [2] + [i for i in xrange(3,n,2) if sieve[i]]

 primes(int(raw_input("Please enter an upper limit ")))

问题发生在第 5 行，我知道实现 [False] * ((n-i*i-1)/(2*i)+1) 可以工作，但我不确定为什么。

Answer 1

您正在尝试用一个元素替换切片覆盖的所有元素:

sieve[i*i::2*i] = [False]

这将从列表中删除元素，但Python仅允许您在不使用步幅的情况下用更少或更多的元素替换切片(如果该部分是连续的，则这是允许的)。无论哪种方式，您都希望将所有这些元素替换为右侧相同数量的元素，因此您可以将筛子中的这些位置设置为 False。

为此，您需要调整右侧的列表，以便有足够的元素来替换每个切片元素:

sieve[i*i::2*i] = [False] * (((n - 1 - i*i) // (2 * i)) + 1)

该公式计算切片在基于 0 的索引系统中覆盖了多少个元素； n - 1 是最高索引，减去起始索引即可得到受影响的元素数量，再除以步幅，加上 1，因为步幅包含第一个元素。

Python 的 xrange() 对象(Python 3 中的 range())使 same calculation ，并包含更长的解释:

Else for step > 0, if n values are in the range, the last one is
lo + (n-1)*step, which must be <= hi-1.  Rearranging,
n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives
the proper value.  Since lo < hi in this case, hi-lo-1 >= 0, so
the RHS is non-negative and so truncation is the same as the
floor.