<p>埃拉托斯泰尼的筛子是这样的:</p>
<pre><code>def sieve(n):
primality_flags = [True]*(n+1)
primality_flags[0] = primality_flags[1] = False
primes = []
for i, flag in enumerate(primality_flags):
if flag:
primes.append(i)
for j in xrange(2*i, n+1, i):
primality_flags[i] = False
return primes
</code></pre>
<p>当外循环到达每个数时,它处理一次,并对每个除以它的素数处理一次。大约1/2个数可被2整除,约1/3可被3整除,依此类推;渐近地讲,每个数被处理的平均次数是1+素数的倒数之和,直到n.<a href="http://en.wikipedia.org/wiki/Meissel%E2%80%93Mertens_constant" rel="nofollow noreferrer">This sum is about ^{<cd1>}</a>,所以这个筛子具有渐近时间复杂度<code>O(n*log(log(n)))</code>,假设算术为常数时间。这真的很好。在</p>
<hr/>
<p>你的功能不会这么做。您的<code>filter</code>遍历<code>numbers</code>中的每个元素,而不管它是否可以被<code>prime</code>整除。对每个素数处理每个元素,直到第一个素数将其分开,并且对素数p的处理将除去<code>numbers</code>元素的大约1/p。设素数序列为p[0]、p[1]、p[2]等,并设<code>numbers</code>的大小序列为n[0]、n[1]、n[2]等,我们得到如下近似的递归:</p>
^{pr2}$
<p>您的算法所花费的时间大致与<code>n</code>值的和成正比,直到<code>numbers</code>为空。我还没有分析这个系列的行为,但是计算表明增长比<code>O(n*log(log(n)))</code>糟糕得多。(编辑:一个<a href="https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf" rel="nofollow noreferrer">analysis</a>我在写这个答案时没有想到它是O((n/log(n))^2)。)</p>