2 
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)工作，但我不知道为什么。

4

1 回答 1

2

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

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()对象（range()在 Python 3 中）进行相同的计算，并包含更长的解释：

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.
于 2015-02-18T11:18:00.687 回答