#1 楼
那不是Eratosthenes的筛子，而是主要的试验部门。您的2个过滤器使所有数字的1/2通过，您3个过滤器使所有剩余数字的2/3通过，等等。
1/2 * 2/3 * 4/5 * 6/7 = 22%的所有数字都通过2、3、5和7的过滤器，因此11的过滤器必须检查所有数字的22％。 Eratosthenes的真实筛子通过标记第11个数字来处理11个数字，即仅占所有数字的9％。不到您百分比的一半。对于更大的素数，您的情况会变得更糟。例如，您的从2到89的质数的过滤器让所有数字的〜12％通过，因此您有97的过滤器检查所有数字的〜12％。虽然Eratosthenes的真正筛子只标出所有数字的1％来对待97，所以这就是为什么它很慢。它正在做太多工作。改进
不堆叠过滤器，而只是使用当前收集的素数，以当前数量简单地进行试验除法，就可以使其速度更快：
from itertools import count
def primes(n):
primes = []
sieve = (x for x in count(2) if all(x % p for p in primes))
for _ in range(n):
primes.append(next(sieve))
return primes
或使用
islice：from itertools import count, islice
def primes(n):
primes = []
sieve = (x for x in count(2) if all(x % p for p in primes))
primes += islice(sieve, n)
return primes
>>> primes(25)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
真实的东西
但这是一个真正的懒人，它是基于特伦特湖我将每个素数添加到其下一个倍数的列表中。当下一个
x的列表为空时，则为素数。否则，我将素数从列表移至下一个倍数。from itertools import count
from collections import defaultdict
def primes(n):
marked = defaultdict(list)
primes = []
for x in count(2):
if x in marked:
for p in marked.pop(x):
marked[x + p].append(p)
else:
primes.append(x)
if len(primes) == n:
return primes
marked[x * x].append(x)
n = 10000的时间（答案末尾的基准代码）：9.330 s original
3.502 s improved1
3.499 s improved2
0.065 s genuine
这就是说，就像我在后面的答案中所做的那样，可以通过使用更少的过滤器（最多不超过当前数字的平方根）来更快地提高您的原始版本和改进版本。
对于无穷大和超越
，正如埃里克·杜米尼尔（Eric Duminil）所展示的，使后者成为无限生成器并不容易，这也使其变得更短。无需构建结果列表并检查是否已完成，只需产生质数即可：
无穷大：
def primes():
marked = defaultdict(list)
for x in count(2):
if x in marked:
for p in marked.pop(x):
marked[x + p].append(p)
else:
yield x
marked[x * x].append(x)
其他解决方案也可以类似地转化为无限生成器，但是，不管怎么说，它们都是不好的。另外，在我的
improved1和improved2中，primes列表不仅是结果，而且还用于过滤，因此无论如何我都需要构建它。作为无限生成器，它更通用。如果愿意，您仍然可以获取前n个列表：
>>> list(islice(primes(), 20))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
还可以将所有素数提高到所需的上限：
>>> *itertools.takewhile(72 .__gt__, primes()),
(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71)
或者如果您都不知道您需要多少，也需要多少，但是您需要某种“足够”的东西，例如，足以使他们的产品超过一百万：
>>> result, product = [], 1
>>> it = primes()
>>> while product < 10**6:
p = next(it)
result.append(p)
product *= p
>>> result
[2, 3, 5, 7, 11, 13, 17, 19]
或者如果您有一个素数，并且想知道它的“多少”素数：
>>> next(islice(primes(), 999999, None))
15485863
或者如果您有素数，并且想知道下一个更大的素数（已授予，有更有效的方法可以做到）：
>>> from operator import indexOf
>>> indexOf(primes(), 15485863) + 1
1000000
请注意，在最后几种情况下，您根本不需要质数列表，因此构建一个素数是浪费的内存。说到内存，生成器（以及我的版本）确实占用了大量内存。以下是上述“无限”解决方案的内存量度和基准，最多n = 1,000,000，下面将显示解决方案：
>>> it = primes()
>>> 89 in it and next(it)
97
内存使用量的测量方法如下：
| time for the first... | tracemalloc for 1,000,000
| 10,000 100,000 1,000,000 | size peak
------------+------------------------------+--------------------------
infinite | 0.068 s 0.971 s 12.450 s | 231,866,275 312,793,599
no_lists | 0.035 s 0.574 s 8.065 s | 143,870,959 226,554,527
lazier | 0.033 s 0.456 s 6.016 s | 36,500,174 36,535,742
recursive | 0.032 s 0.473 s 6.116 s | 72,169 109,109
twostep | 0.015 s 0.217 s 2.897 s | 71,986 108,926
因此，上述“无限”解决方案需要数百兆字节才能生成前百万个素数，即每个素数数百个字节。非常多。让我们看看为什么通过在
global marked函数中先做primes()来进行事后检查。我们将看到标记了将近一百万个复合词，字典占用了84 MB： br /> import tracemalloc
tracemalloc.start()
it = primes()
prime = next(islice(it, 9999999, None))
size, peak = tracemalloc.get_traced_memory()
标记的复合材料占用32 MB，标记的素数占用28 MB：
>>> it = primes()
>>> next(islice(it, 999999, None))
15485863
>>> from sys import getsizeof
>>> len(marked), getsizeof(marked)
(999919, 83886176)
总计上表中tracemalloc报告的总大小为232 MB：
>>> sum(map(getsizeof, marked.values()))
87992872
>>> from collections import Counter
>>> Counter(map(len, marked.values()))
Counter({1: 999845, 2: 69, 3: 4, 4: 1})
由于大多数标记素数列表无论如何都只包含一个素数，因此我们仅将第一个素数存储在组合中。如果更多质数要标记该合成，则将其移至下一个倍数：
no_lists：
>>> sum(map(getsizeof, marked))
31983680
>>> from itertools import chain
>>> sum(map(getsizeof, chain.from_iterable(marked.values())))
27999972
如上表所示，这使其速度更快并节省了大量内存。
在我的另一个答案中，我表明，一旦发现新的质数
marked[x * x]，过早设置x是浪费的。让我们从那里重写更好的版本作为无限生成器。这里m是下一个标记质数，一旦到达m2 = m 2，它将立即开始标记。懒惰的人：小多了。但是，它会再次创建一个
marked列表，以便将primes更新为下一个标记质数。不是过早输入m并没有建立marked[x * x]列表？是的，我们可以！我们将素数列表用于什么目的？就像使用更缓慢的素数流一样。但这就是我们正在写的！素数生成器。因此我们可以递归使用它。我们的主要素数生成器迭代器将使用较慢的素数生成器迭代器。但是，速度较慢的人从何处得到其标记素数？如果需要的话，从另一个甚至更慢的进度。等等。可能是无限迭代器的无限堆栈。然后：
>>> 84 + 88 + 32 + 28
232
我们看到迭代器有五个级别。顶层迭代器（我们直接使用的迭代器）具有546个标记质数，最大的是3931。这是有道理的，因为下一个较大的质数是3943，它开始在39432处进行标记，该值大于百万分之一的质数：
def primes():
marked = {}
for x in count(2):
if x in marked:
p = marked.pop(x)
while (x := x + p) in marked:
pass
marked[x] = p
else:
yield x
marked[x * x] = x
到目前为止，下一个较低的水平仅需要产生18个素数达到61。这是正确的，因为下一个较大的素数67仅在672 = 4489处开始标记，远高于顶级迭代器接下来需要质数3943。依此类推，直到第五级和最低级别到目前为止只需要其初始
primes。所有级别中只有数百个素数相加，因此，与第一个“无限”解决方案相比，难怪此解决方案所需的内存更少大约少3000倍，大约只有100 KB。而且，它的优势将随着大量质数的增加而增加，因为较早的解决方案需要O（n）内存，而递归解决方案则需要O（sqrt（n））内存（不确定质数的密度如何影响它）。 />最后但并非最不重要的一点是，这是一个小变化，我分别处理质数2，然后将所有内容移动两倍快，这使整体解决方案的速度快一倍（再次参见上表）：
两步操作：
def primes():
yield 2
primes = [2]
markers = iter(primes)
marked = {}
m = next(markers)
m2 = m * m
for x in count(3):
if x == m2:
while (x := x + m) in marked:
pass
marked[x] = m
m = next(markers)
m2 = m * m
elif x in marked:
p = marked.pop(x)
while (x := x + p) in marked:
pass
marked[x] = p
else:
yield x
primes.append(x)
基准代码1的代码：
def primes():
yield 2
marked = {}
markers = primes()
m = next(markers)
m2 = m * m
for x in count(3):
if x == m2:
while (x := x + m) in marked:
pass
marked[x] = m
m = next(markers)
m2 = m * m
elif x in marked:
p = marked.pop(x)
while (x := x + p) in marked:
pass
marked[x] = p
else:
yield x
评论
\ $ \ begingroup \ $
要清楚，第一个改进是将算法从递归转换为迭代，避免了调用所有lambda的开销，实际测试操作是相同的。我觉得措词不是很清楚，因为“让所有数字的2/3通过”可以表明6将由filter_2和filter_3检查，而不是在filter_2测试中弹出。我不得不重新阅读几次以细枝末节，分别描述每个过滤器，然后显示将它们堆叠的结果。的确，这更多是语法上的抱怨。
\ $ \ endgroup \ $
–凯塔尔
20-10-28在14:03
\ $ \ begingroup \ $
@Kaithar是的，操作相同。我使用相应的质数和all（...）进行过滤，而不是自己过滤的堆叠式过滤器。关于“让所有数字的2/3通过”：既是孤立的又是组合的。如果对所有整数都使用filter_3，则每三个整数都会被过滤掉。如果在filter_2允许通过的内容上使用filter_3（即，奇数整数），则filter_3也会删除每第三个数字（即3，但不是5或7，然后是9但不是11或13，然后是15但不是17或19，等等） 。对于filter_5，它的规则性较差，但仍然允许5个数字中有4个...
\ $ \ endgroup \ $
–凯利·邦迪（Kelly Bundy）
20-10-28在15:22
\ $ \ begingroup \ $
这就是我将其从递归更改为迭代的意思。我仔细检查百分比的方法是相反的...因为2的倍数的1/3都是3的倍数（很明显），所以移除和剩余的倍数的比例是相同的，因此每个过滤器都独立于其如果输入集是统一的，则为前任。但是就像我说的那样，这纯粹是隐式“测试所有数字”与显式“测试剩余数字”之间的学问区别。真正重要的是，对原汁原味的标记下一个正方形的方法到底有多优雅。
\ $ \ endgroup \ $
–凯塔尔
20-10-28在16:23
\ $ \ begingroup \ $
另外，您可以轻松地将其转换为无限质数生成器：tio.run/##bY/NasMwEITveoqBYiI1JiTNLZB36L2UYqx1u1SWFlkBpS/…
\ $ \ endgroup \ $
–埃里克·杜米尼尔（Eric Duminil）
20-10-28在18:30
\ $ \ begingroup \ $
@EricDuminil我没有读过那部分论文，部分是因为我不了解Haskell，所以在某些时候已经不明白他们在说什么。我确实尝试了只有2和3的微型车轮，但我考虑了更大的车轮，但后来觉得解决方案已经变得足够复杂了。就是说，我发现了另一个改进，使其变得更快，更简单，所以也许我会尝试将轮子与之结合。
\ $ \ endgroup \ $
–凯利·邦迪（Kelly Bundy）
20年11月1日，11：32
#2 楼
回到根源-变得懒惰！（这个方向与我的第一个答案不同，而且它的长度/长度足以使我不想混淆它们。）
我们可以极大地改善您的方法通过不急于添加过滤器，而是仅添加不超过当前候选编号平方根的过滤器。我认为这是一种简洁的方法。基准测试结果：
n: 10,000 100,000 1,000,000 2,000,000
original_rooted_eval 0.075 s 2.036 s 59.669 s 162.764 s
original_rooted_asmod 0.081 s 2.128 s 56.001 s 151.860 s
original_rooted_default1 0.082 s 2.095 s 56.286 s 151.667 s
original_rooted_default2 0.075 s 1.895 s 50.088 s 134.353 s
original_rooted_rmod 0.041 s 1.050 s 28.101 s 75.745 s
improved_rooted 0.033 s 0.806 s 21.825 s 55.485 s
genuine_rooted 0.060 s 0.799 s 10.073 s 21.809 s
genuine 0.073 s 0.952 s 12.662 s 27.009 s
n = 10,000时，您的原始版本和改进版本的速度几乎是我真正的Eratosthenes版本的两倍。这比以前快了一百倍。但是，当n = 1,000,000时，真正的数字已经出现问题了。
正如论文还指出的那样，部分缓慢性（大部分）来自于对所有素数都低于当前候选数的素数进行试算。这类似于此单数素数检查：
def is_prime(x):
return all(x % d for d in range(2, x))
我们应该只尝试对素数的平方根求素。如果候选\ $ x \ $具有除数\ $ d> \ sqrt {x} \ $，则e = \ $ \ frac {x} {d} <\ sqrt {x} \ $将是另一个除数，我们会在\ $ \ sqrt {x} \ $下找到它。
def is_prime(x):
return x >= 2 and all(x % d for d in range(2, isqrt(x)+1))
现在我们如何在解决方案中做到这一点？在
original中，这意味着仅创建不超过当前数字平方根的过滤器。在我的improved中，这意味着不遍历所有primes，而仅遍历平方根。因此：在4时开始过滤2，在9时开始过滤3，在25时开始过滤5，依此类推。为此，请跟踪下一个质数平方（即， 4、9、25等），并在i中添加该质数的索引primes。每当您到达下一个素数平方时，不要将其视为素数，而是添加下一个过滤器。生根：
def original_rooted_eval(n):
sieve = count(2)
primes = []
next_prime_square, i = 4, 0
for _ in range(n):
while (nprime := next(sieve)) == next_prime_square:
sieve = filter(eval(f"lambda x: x % {primes[i]} != 0"), sieve)
i += 1
next_prime_square = primes[i] ** 2
primes.append(nprime)
return primes
或与
asmod一起使用： sieve = filter(asmod(primes[i]), sieve)
或使用带有默认参数的
lambda： sieve = filter(lambda x, p=primes[i]: x % p != 0, sieve)
而且不需要
!= 0，只会减慢它的速度。我们可以使用余数的真相： sieve = filter(lambda x, p=primes[i]: x % p, sieve)
现在很明显，我们可以简单地使用质数的右侧取模方法：
sieve = filter(primes[i].__rmod__, sieve)
这是所有不同的版本您在上面的基准测试结果中看到的原始版本。因此，我改为建立一个已经过滤质数的额外列表：
def improved_rooted(n):
primes = []
filters = []
next_prime_square, i = 4, 0
for x in count(2):
if x == next_prime_square:
filters.append(primes[i])
i += 1
next_prime_square = primes[i] ** 2
else:
for p in filters:
if not x % p:
break
else:
primes.append(x)
if len(primes) == n:
return primes
生根
for p in primes：直到达到\ $ x ^ 2 \ $。因此从这个意义上说，if p*p > x: break已经扎根。但是，如果我们从不走到\ $ x ^ 2 \ $，那么即使浪费了。因此，将其完全放到genuine中，直到达到其平方为止。然后将其放入下一个倍数genuine（其中marked[x * x]现在是原始整数genuine，所以实际上是marked）。def genuine_rooted(n):
primes = []
marked = defaultdict(list)
next_prime_square, i = 4, 0
for x in count(2):
if x == next_prime_square:
marked[x + primes[i]].append(primes[i])
i += 1
next_prime_square = primes[i] ** 2
elif x in marked:
for p in marked.pop(x):
marked[x + p].append(p)
else:
primes.append(x)
if len(primes) == n:
return primes
包括完整解决方案的基准代码： >
from timeit import timeit
from itertools import count
from collections import defaultdict
from math import isqrt
def original_rooted_eval(n):
sieve = count(2)
primes = []
next_prime_square, i = 4, 0
for _ in range(n):
while (nprime := next(sieve)) == next_prime_square:
sieve = filter(eval(f"lambda x: x % {primes[i]} != 0"), sieve)
i += 1
next_prime_square = primes[i] ** 2
primes.append(nprime)
return primes
def original_rooted_asmod(n):
sieve = count(2)
primes = []
next_prime_square, i = 4, 0
def asmod(a):
def inner(x):
return x % a != 0
return inner
for _ in range(n):
while (nprime := next(sieve)) == next_prime_square:
sieve = filter(asmod(primes[i]), sieve)
i += 1
next_prime_square = primes[i] ** 2
primes.append(nprime)
return primes
def original_rooted_default1(n):
sieve = count(2)
primes = []
next_prime_square, i = 4, 0
for _ in range(n):
while (nprime := next(sieve)) == next_prime_square:
sieve = filter(lambda x, p=primes[i]: x % p != 0, sieve)
i += 1
next_prime_square = primes[i] ** 2
primes.append(nprime)
return primes
def original_rooted_default2(n):
sieve = count(2)
primes = []
next_prime_square, i = 4, 0
for _ in range(n):
while (nprime := next(sieve)) == next_prime_square:
sieve = filter(lambda x, p=primes[i]: x % p, sieve)
i += 1
next_prime_square = primes[i] ** 2
primes.append(nprime)
return primes
def original_rooted_rmod(n):
sieve = count(2)
primes = []
next_prime_square, i = 4, 0
for _ in range(n):
while (nprime := next(sieve)) == next_prime_square:
sieve = filter(primes[i].__rmod__, sieve)
i += 1
next_prime_square = primes[i] ** 2
primes.append(nprime)
return primes
def improved_rooted(n):
primes = []
filters = []
next_prime_square, i = 4, 0
for x in count(2):
if x == next_prime_square:
filters.append(primes[i])
i += 1
next_prime_square = primes[i] ** 2
else:
for p in filters:
if not x % p:
break
else:
primes.append(x)
if len(primes) == n:
return primes
def genuine_rooted(n):
primes = []
marked = defaultdict(list)
next_prime_square, i = 4, 0
for x in count(2):
if x == next_prime_square:
marked[x + primes[i]].append(primes[i])
i += 1
next_prime_square = primes[i] ** 2
elif x in marked:
for p in marked.pop(x):
marked[x + p].append(p)
else:
primes.append(x)
if len(primes) == n:
return primes
def genuine(n):
marked = defaultdict(list)
primes = []
for x in count(2):
if x in marked:
for p in marked.pop(x):
marked[x + p].append(p)
else:
primes.append(x)
if len(primes) == n:
return primes
marked[x * x].append(x)
funcs = [
original_rooted_eval,
original_rooted_asmod,
original_rooted_default1,
original_rooted_default2,
original_rooted_rmod,
improved_rooted,
genuine_rooted,
genuine,
]
# Correctness check
n = 10**4
expect = funcs[0](n)
for func in funcs[1:]:
print(func(n) == expect, func.__name__)
print()
width = max(len(func.__name__) for func in funcs) + 2
sizes = 10**4, 10**5, 10**6, 2 * 10**6
rounds = 5
# tss[s][f] := list of times for size #s and function #f.
tsss = []
for n in sizes:
tss = [[] for _ in funcs]
tsss.append(tss)
for r in range(rounds):
print(f'{n=:,} round={r+1}/{rounds}')
for func, ts in zip(funcs, tss):
# t = n / 1e5 # fake for faster development
t = timeit(lambda: func(n), number=1)
ts.append(t)
# print(func.__name__, t) # Show results as they happen
print('n:'.rjust(width), *(f'{n:8,} ' for n in sizes))
for f, func in enumerate(funcs):
print(func.__name__.rjust(width), end=' ')
for tss in tsss:
print(' %.3f s ' % min(tss[f]), end='')
print()
print()
#3 楼
提出既“有趣”又“技术上正确”的东西的奖励点；但这就是停止的地方。肯定不是很快。想想这里发生了什么：对于
eval或asmod的每次调用，您都在生成器上链接了具有新功能的另一层过滤器。那根本无法扩展。使用简单的方法最好，只用一个数据结构来存储过滤器。用list或array的布尔值或set的整数值进行实验，看看哪个具有最佳性能。评论
\ $ \ begingroup \ $
您将如何使用列表/数组/集合来编写它？
\ $ \ endgroup \ $
–凯利·邦迪（Kelly Bundy）
20-10-26在17:13
\ $ \ begingroup \ $
@HeapOverflow这是一个常见的问题，有一个专用的完整标签：codereview.stackexchange.com/questions/tagged/…
\ $ \ endgroup \ $
– Reinderien
20-10-26在17:15
\ $ \ begingroup \ $
但是他们并没有真正筛查Eratosthenes。我想知道您的假冒版本。
\ $ \ endgroup \ $
–凯利·邦迪（Kelly Bundy）
20-10-26在17:30
\ $ \ begingroup \ $
@Reinderien我主要是想制作一个可以无限期运行的生成器，该生成器不适用于列表，数组等。
\ $ \ endgroup \ $
– Jay jayjay
20-10-26在17:38
\ $ \ begingroup \ $
@jayjayjay可能有一个分段的，渐进式的筛子，它可以无限期地运行，但仍基于数据结构。
\ $ \ endgroup \ $
– Reinderien
20-10-26在17:55
#4 楼
我中的“纯粹主义者”说，任何不以建立有限的数字表开始的解决方案都不是Eratosthenes的筛子，也不是任何不将所有信息（数字，交叉）保留在一个表中的解决方案（数据结构） 。为什么？在Eratosthenes时代，他不得不创建表，在完成表创建后，他开始删除数字（不是从表中删除数字）。最终结果是相同的表，除了非质数（当存在时）被“划掉”。表'。对于这种抽象，可以使用np.array。这将是一行一列的表，其中数组值表示“ cross off”，而索引表示数字。在初始状态下，所有数字都不会被划掉，即True：
sieve = np.ones(max_value + 1, dtype=np.bool)
通过将值设置为'False'
sieve[:2] = False
遍历从第一个质数（2）到平方根+ 1的整数部分的所有数字，如果数字未“相减”（即对应索引的值为是的），
“交叉”数字以数字的平方开头，并以数字为步长。错误，所有“非交叉”索引值均为True。
对我来说，这更像是模仿Eratosthenes原始筛子的纸和铅笔（或黏土和手写笔）（您的行驶里程可能会有所不同）。作为简单函数：
for i in range(2, isqrt(max_value)+1):
if sieve[i]:
sieve[i*i::i] = False
现在完全不同：在《生命，宇宙和其他一切》（python.org）的神圣页面上，有一个SimplePrograms：“ 20行：质数筛子带有花式生成器” ：
import numpy as np
from math import isqrt
def primes(max_value):
sieve = np.ones(max_value + 1, dtype=np.bool)
sieve[:2] = False
for i in range(2, isqrt(max_value)+1):
if sieve[i]:
sieve[i*i::i] = False
return np.nonzero(sieve)[0] # return only primes
评论
这不是Eratosthenes的筛子@trentcl：我最喜欢的论文之一，应该广为人知。
您仍然可以使用lambda而不依赖eval；您只需要预绑定nprime作为默认参数：sieve = filter（lambda x，nprime = nprime：x％nprime！= 0，sieve）。就是说，如果您需要使用Python定义的函数（def或lambda）来使用过滤器，则最好只使用等效的listcomp或genexpr（不幸的是，由于绑定晚，所以比较难），或者找到一种使其真正实现的方法使用内置的C语言实现。在这种情况下，您可以执行sieve = filter（nprime .__ rmod__，sieve），效果相同（nprime和所有sieve元素均为int）。
请不要更新您问题中的代码以合并答案中的反馈，因为这样做有悖于“代码审阅”的“问题+答案”风格。这不是您应该在其中保留最新版本的论坛。请参阅*收到答复后您可能会做什么或可能不会做什么。
@EricDuminil我想Python版本会使用itertools做wheel2357 = cycle（[2，4，2，4，6，2，6，4，2，4，4，6，6，6，6，4，2，6 ，4，4，8，4，2，4，2，4，8，6，4，6，2，4，6，2，6，6，4，2，4，4，6，2，6，4 ，2，4，2，10，2，10]）和质数= chain（[2，3，5，7]，sieve（accumulate（wheel2357，initial = 11）））..