解释这个素数生成器函数,我无法理解[python]

Question

def primes(n): 
    if n==2: return [2]
    elif n<2: return []
    s=range(3,n+1,2)
    mroot = n ** 0.5
    half=(n+1)/2-1
    i=0
    m=3
    while m <= mroot:
        if s[i]:
            j=(m*m-3)/2
            s[j]=0
            while j<half:
                s[j]=0
                j+=m
        i=i+1
        m=2*i+3
    return [2]+[x for x in s if x]

您好,我在这里找到了这个函数http://code.activestate.com/recipes/366178-a-fast-prime-number-list-generator/而且我被卡住了.我不明白这一点.我认为它使用素数的一些属性,但所有那些单字母变量都是如此神秘.你可以请一些亮点吗？

我理解:mroot是你要检查素数的数字的限制,我知道该函数将列表s更改为0来标记倍数.我也理解最后的列表综合,我理解s.

但为什么一半？什么是j？什么是米？

你能否发表评论？

Answer 1

逐行细分:

def primes(n): 
    if n==2: return [2]

此函数返回素数列表<= n.所以如果n == 2,那个列表只包含2.很容易.

    elif n<2: return []

在这里,2以下没有素数,所以返回一个空列表.

    s=range(3,n+1,2)

所以s是一个以3开头并且去的奇数列表n + 1.s代表筛子 - 这是一种筛分算法,这意味着复合(非素数)数字将从列表中筛选出来.实际上,他们将被"划掉".有关筛分算法的详细说明,请参见下文.

    mroot = n ** 0.5

因为它是筛子,所以一旦我们达到了平方根,我们就可以停止算法n.

    half=(n+1)/2-1

这是s长度的明确公式; 它可以替换为len(s),但可能需要更长的时间来计算n的大值.这对于终止算法的某些部分也很有用.

    i=0
    m=3

我是我们的指数; 我只需走过筛子,检查每个值.如果该值为0,则该数字已被"划掉",因为它不是素数.m只是s[i]在任何特定时刻的价值; 后一行保持更新.

    while m <= mroot:
        if s[i]:

自s[i]评估以来True,它尚未从列表中删除.这意味着它是最好的!所以现在我们必须弄清楚列表中的哪些数字是它们的倍数s[i]- 它们都是非素数,并且应该从列表中划掉.

            j=(m*m-3)/2
            s[j]=0

现在开始有趣了.因为筛子不是连续数字的列表,而是奇数列表,我们必须弄清楚我们的素数的倍数在哪里s.在这种情况下,我们的素数是3,所以我们需要找到9,15,21,27的索引......(我们不必找到6,12,18 ......因为它们是偶数,所以不在列表中).这种寻找指数的特殊技术非常聪明,因为作者已经发现,一旦特定素数的所有倍数都被划掉,就可以跳过它们.这意味着我们的素数的第一个未划掉的多数实际上是该素数的平方.(因此,举例来说,如果主要是7,7*3 = 21和7*5 = 35就已经被划掉了,所以7,第一多,我们要处理的是7*7)一旦使感觉,很容易看出9 in的位置s是(9 - 3)// 2(其中//是地面划分).

            while j<half:
                s[j]=0
                j+=m

现在它又变得容易了.我们发现9; 现在我们必须找到15 = 9 + 3 + 3.由于s只包含奇数,它只是每个数字列表的一半; 然后跳过6,我们只需要添加3 j.我们这样做只要j小于half- 换句话说,只要j小于长度s.

        i=i+1
        m=2*i+3

同样,easy - i只是列表的索引,m而是原始数字的值.(你可以测试一下,看看为什么:[2 * i + 3 for i in range(10)].)

    return [2]+[x for x in s if x]

而瞧 -过滤零出筛,将[2],你有质数的列表.

关于这个算法最令人困惑的事情与作者所采用的快捷方式有关,这使得运行速度更快,但却使基本概念变得模糊.(事实上​​,人们可以采取更多的捷径,但这是另一篇文章.)这是一个更简单的筛子,显示了基本的想法:

>>> numbers = range(40)
>>> numbers[1] = 0    # 1 isn't prime
>>> for i in numbers:
...     if i:
...         for j in range(i + i, len(numbers), i):
...             numbers[j] = 0
... 
>>> [n for n in numbers if n]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

为了拼写这一切,第一个数字看起来像这样:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10...]

然后...

[0, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10...]
[0, 0, 2, 3, 0, 5, 0, 7, 0, 9, 0...]
[0, 0, 2, 3, 0, 5, 0, 7, 0, 0, 0...]

等等.