python - 埃拉托色尼筛法

Question

我有这段代码我不太明白，因为我一周前才开始学习 Python。

import numpy as np
import time

start_time=time.clock()

def Sieb(n):                           #Sieve
    Eins = np.ones(n, dtype=bool)      #Eins is just german for One
    Eins[0] = Eins[1] = False          #->I don't quite understand what
    for i in range(2, n):              #this one does.
        if Eins[i]:
            Eins[i*i::i] = False       #Does this make the ones = zero?
    return np.flatnonzero(Eins)


print Sieb(1000000)
print start_time

所以，我理解筛子的概念(我猜)，但我不确定它是如何在这里实现的。自身的倍数在哪里达到 0 以及 np.flatnonzero 是如何得出素数的，因为在那之前，它们只是 1和 0?

希望您能理解并帮助我。 :)

Answer 1

让我们逐步了解它。

Eins = np.ones(n, dtype=bool)

这将创建一个大小为 n 的新数组，类型为 bool , 和所有的。由于类型，“一”表示 True .该数组代表我们要测试素数的所有数字，其中 True表示数字是质数，False意思不是。因此，我们从所有标记为(潜在)素数的数字开始。

Eins[0] = Eins[1] = False

现在我们设置 0 th 和 1 st 元素到 False : 0 和 1 都不是素数。

for i in range(2, n):

接下来，我们将遍历所有剩余的数字(从 2 开始)。我们可以只求 n 的平方根，但为了简单起见，我们遍历所有数字。

    if Eins[i]:

如果i数组的第 th 个值是 True , 这意味着 i是质数。第一次输入此条件是使用 i=2 .接下来，我们要从主要候选人中删除我们数字的所有倍数:

        Eins[i*i::i] = False

我们可以把这一行看成是 Eins[2*i::i] = False , 从 i*i 开始只是一个优化¹。如果 2 是素数，则意味着 2*2、3*2、4*2... 不是，因此我们将倍数设置为 False .索引符号代表“从 i*i 到结束”(由冒号之间的空格表示)“，以 i 为步长”。该语句产生数字 i*i , i*(i+1) , i*(i+2) , ..., 所以 i 的所有倍数还没有被标记为“不是素数”。

return np.flatnonzero(Eins)

这只是返回值为 True 的所有索引，即找到的所有素数。

---

1:关于 i*i 的一句话: 我们可以从i的正方形开始，因为任何数字 j*i (对于 j < i )当我们在 j 时已经被标记为非素数.

---

这是一个演示，它适用于 n=15 :

我们从填充了 .ones 的数组开始:

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
[T, T, T, T, T, T, T, T, T, T, T, T, T, T, T]

然后我们清空Eins[0]和 Eins[1] :

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
[F, F, T, T, T, T, T, T, T, T, T, T, T, T, T]

现在我们开始遍历范围，从 i=2 开始, 然后我们删除所有以 2*2=4 开头的 2 的倍数:

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
[F, F, T, T, F, T, F, T, F, T, F, T, F, T, F]

i=3 , 删除所有以 3*3=9 开头的 3 的倍数:

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
[F, F, T, T, F, T, F, T, F, F, F, T, F, T, F]

请注意，我们不必删除 6 , 因为它已经被 i=2 删除了.

当 i=4 ，我们跳过删除，因为 Eins[i]是False .来自 i=5之后，什么也没有发生，因为方 block (25, 36, ...) 比数组大。最后，我们使用 flatnonzero并获取值为 True 的所有索引:

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
[F, F, T, T, F, T, F, T, F, F, F, T, F, T, F]
       2  3     5     7          11    13