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数组的第一个值为 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之后，什么也没有发生，因为正方形 (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