python - 解释这个素数生成器函数，我无法理解[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，以标记倍数。后面的list comprehesion我也看懂了，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代表 sieve——这是一个筛选算法，这意味着复合(非素数)数字将从列表中筛选出来。实际上，它们将被“划掉”。有关筛选算法的详细说明，请参见下文。

    mroot = n ** 0.5

因为它是一个筛子，我们可以在达到 n 的平方根后停止算法。 .

    half=(n+1)/2-1

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

    i=0
    m=3

I 是我们的索引；我只是简单地通过筛子，检查每个值。如果值为 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 在 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

同样，简单 -- 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...]

等等。