<p>那不是埃拉托舍内斯的筛子,尽管看起来是。事实上更糟。筛是寻找素数的最佳算法。</p>
<p>见<a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes</a></p>
<p><strong>编辑</strong>:我已将<a href="https://stackoverflow.com/a/9302299/711085">https://stackoverflow.com/a/9302299/711085</a>修改为一行(最初它不是真正的筛子,但现在它是。。。可能……:</p>
<pre><code>reduce( (lambda r,x: r-set(range(x**2,N,x)) if (x in r) else r),
range(2,N), set(range(2,N)))
</code></pre>
<p>演示:</p>
<pre><code>>>> primesUpTo(N): lambda N: reduce(...)
>>> primesUpTo(30)
{2, 3, 5, 7, 11, 13, 17, 19}
</code></pre>
<hr/>
<p>遗憾的是,我认为虽然这在函数式编程语言中是有效的,但在python中由于非持久(共享状态和不可变)的数据结构,它可能没有那么有效,python中的任何筛子都需要使用变异来获得可比的性能。如果我们非常想的话,我们还可以把它塞进一个一行程序中。但首先。。。</p>
<p>普通筛:</p>
<pre><code>>>> N = 100
>>> table = list(range(N))
>>> for i in range(2,int(N**0.5)+1):
... if table[i]:
... for mult in range(i**2,N,i):
... table[mult] = False
...
>>> primes = [p for p in table if p][1:]
>>> primes
[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]
</code></pre>
<p>我们现在可以在同一行上定义和调用匿名函数,还可以使用<code>[...].__setitem__</code>进行内联变异,使用<code>... and foo</code>在返回<code>foo</code>时计算<code>...</code>:</p>
<pre><code>>>> primesUpTo = lambda N: (lambda table: [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] for i in range(2,int(N**0.5)+1) if table[i]] and [p for p in table if p][1:])(list(range(N)))
>>> primesUpTo(30)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
</code></pre>
<p>继续在恐惧中畏缩,一行代码扩展了(奇怪的美丽,因为你几乎可以直接翻译控制流,但却严重滥用了所有东西):</p>
<pre><code>lambda N:
(lambda table:
[[table.__setitem__(mult,False) for mult in range(i**2,N,i)]
for i in range(2,int(N**0.5)+1) if table[i]]
and [p for p in table if p][1:]
)(list(range(N)))
</code></pre>
<p>在我的机器上,这一行变异版本在大约10<sup>8</sup>时放弃,而原始变异版本在大约10<sup>9</sup>时放弃,内存不足(奇怪)。</p>
<p>最初的<code>reduce</code>版本在10<sup>7<sup>时放弃。因此,也许并不是<em>效率低下(至少对于您可以在计算机上处理的数字而言)。</p>
<p><strong>edit2</strong>似乎可以更简洁地滥用副作用:</p>
<pre><code>reduce( (lambda r,x: (r.difference_update(range(x**2,N,x)) or r)
if (x in r) else r),
range(2,N), set(range(2,N)))
</code></pre>
<p>它在大约10<sup>8<sup>时放弃,与一行变异版本相同。</p>
<p><strong><em>edit3:</em></strong>这个<a href="http://ideone.com/Qyzjp" rel="nofollow noreferrer">runs at</a>O(N)<a href="http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth" rel="nofollow noreferrer">empirical complexity</a>,而没有<code>difference_update</code>,它在<a href="http://ideone.com/vZB5z" rel="nofollow noreferrer">O(n^2.2) complexity</a>运行。</p>
<p>将缩小的范围限制在上限的sqrt内,并且工作<a href="http://ideone.com/gl1h9" rel="nofollow noreferrer">with odds only</a>,这两种情况都会导致额外的速度增加(<em>2x</em>并且相应地<em>1.6x</em>):</p>
<pre><code>reduce( (lambda r,x: (r.difference_update(range(x*x,N,2*x)) or r)
if (x in r) else r),
range(3, int((N+1)**0.5+1), 2),
set([2] + range(3,N,2)))
</code></pre>