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

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.

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

Looking at a prime sieve program but unsure why it keeps coming up with an error about slice length

python

primes

sieve

python-2.7