埃拉托色尼筛法
Sieve of Eratosthenes Understanding
我有这段代码我不太明白，因为我刚开始学习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?
希望您能理解并帮助我。 :)
让我们逐步了解它。
Eins = np.ones(n, dtype=bool)
这将创建一个新数组，大小为 n，类型为 bool，并且全部为 1。由于类型的原因，"one" 表示 True。该数组代表我们想要测试素数的所有数字，True 表示该数字是素数，False 表示不是。所以我们从所有标记为（潜在）素数的数字开始。
Eins[0] = Eins[1] = False
现在我们将第0和第1个元素设置为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。索引符号代表 "from i*i until the end"（由冒号之间的空 space 表示）“，以 i 为步长”。此语句生成数字 i*i、i*(i+1)、i*(i+2)、...，因此尚未标记为 "not a prime" 的所有 i 的倍数。
return np.flatnonzero(Eins)
这只是 returns 值为 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
我有这段代码我不太明白，因为我刚开始学习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?
希望您能理解并帮助我。 :)
让我们逐步了解它。
Eins = np.ones(n, dtype=bool)
这将创建一个新数组，大小为 n，类型为 bool，并且全部为 1。由于类型的原因，"one" 表示 True。该数组代表我们想要测试素数的所有数字，True 表示该数字是素数，False 表示不是。所以我们从所有标记为（潜在）素数的数字开始。
Eins[0] = Eins[1] = False
现在我们将第0和第1个元素设置为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。索引符号代表 "from i*i until the end"（由冒号之间的空 space 表示）“，以 i 为步长”。此语句生成数字 i*i、i*(i+1)、i*(i+2)、...，因此尚未标记为 "not a prime" 的所有 i 的倍数。
return np.flatnonzero(Eins)
这只是 returns 值为 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:
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:
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