未能理解一些素筛语法

Question

谁能帮我逐行通过这个初筛？我正在尝试开发自己的筛子，但大多数更快的筛子都包含我不理解的语法（比如我发表评论的行）。很抱歉，如果这是一个新手问题——如果您有任何链接可以帮助我进行筛选写作，我们将不胜感激。

def rwh_primes1(n):
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2) # What does the '[True]' mean?
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]: # The same complaint as in line 3, I don't understand the variable 'sieve'
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) # how is sieve used here - it seems to be as a list but i'm unsure
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]] # 'sieve' is confusing me here yet again.

Answer 1

我会把每行代码的意思用斜体字，我的评论用普通字体。

sieve = [True] * (n/2)

声明一个新的局部变量sieve并将其初始化为值[True] * (n/2)。这个表达式是什么意思？ [True] 是仅包含布尔值 True 的单元素列表。将列表乘以数字会重复列表，因此 sieve 现在是一个包含所有 True 值的 n/2 元素列表。

for i in xrange(3, int(n**0.5)+1, 2):

以 2 为步长开始计数，从 3 开始到 sqrt(n) 结束。这种特定的范围选择是对 Sieve 算法的优化：我们可以计算所有从 1 到 n 的步长为 1，但效率会降低。

if sieve[i/2]:

查看 sieve 列表的第 i/2 个元素。如果是True，则继续if分支。作者使用i/2来补偿代码以2为步数的事实。这样您可以使用更短的列表并使用更少的内存。

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

将sieve的每个第i个元素更新为False，从i*i/2开始。 sieve[i*i/2::i]是称为 slice notation - 因为它出现在赋值的左侧，此代码将更新 sieve 的那一部分。右侧是列表乘以数字技巧的重复。它计算出一个长度正确的全 False 列表。

return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

此代码只是将 sieve 中的 True/False 值转换为质数列表。该计算通过将每个 True 值的索引乘以 2 来补偿 sieve 不包含任何偶数的事实。

Answer 2

假设 n=7:

    sieve = [True] * (n/2) # What does the '[True]' mean?

制作长度为 n 一半的布尔真值列表。例如，sieve = [True,True,True]（因为 3.5 是分数长度，它会在 python2 中向下舍入）

所以 xrange(3,int(n**0.5)+1,2) 将是一个给我们这个序列的生成器：[]

    for i in 
        if sieve[i/2]: # The same complaint as in line 3, I don't understand the variable 'sieve'
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) # how is sieve used here - it seems to be as a list but i'm unsure
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]] # 'sieve' is confusing me here yet again.

当我们看到 [i::2] 或类似的意思时，我们会以重复的间隔对列表进行切片。所以如果 mylist 包含 (0..19):

>>> mylist = range(20)
>>> mylist[0::1]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>> mylist[0::2]
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
>>> mylist[0::3]
[0, 3, 6, 9, 12, 15, 18]

自己尝试一下，熟悉它。所以在这种情况下 sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) 会将列表中的每个第 i 个值设置为 False。

未能理解一些素筛语法

Failure to understand some prime sieve syntax

python

primes

sieve