0

Could someone walk me line-by line through this prime sieve? I'm attempting to develop my own sieve but most of the faster ones contain syntax that I don't understand (like the lines i've made comments on). Sorry if this is sort of a newbie question -- also if you have any links that could help me with sieve writing they'd be greatly appreciated.

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.
4

2 回答 2

4

我将每行代码的含义以斜体字表示，并以普通文本添加我的注释。

sieve = [True] * (n/2)

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

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

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

if sieve[i/2]:

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

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

sieve更新to的每个第 i 个元素False，从 i*i/2 开始。 sieve[i*i/2::i]称为切片表示法-因为它出现在赋值的左侧，此代码将更新sieve. 右侧是 list-times-number 技巧的重复。它计算False正确长度的所有列表。

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

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

于 2016-03-01T23:43:02.027 回答
1

假设 n=7：

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

列出长度为 n 一半的布尔 True 值。例如，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。

于 2016-03-01T23:47:45.890 回答