回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我正在尝试学习python,我想尝试开发自己的prime sieve将是下午的一个有趣的问题。到目前为止,当需要的时候,我只需要导入一个我在网上找到的Eratosthenes筛的版本——我用这个作为我的基准。你知道吗</p>
<p>在尝试了几个不同的优化之后,我认为我已经编写了一个相当不错的筛选:</p>
<pre><code>def sieve3(n):
top = n+1
sieved = dict.fromkeys(xrange(3,top,2), True)
for si in sieved:
if si * si > top:
break
if sieved[si]:
for j in xrange((si*2) + si, top, si*2): [****]
sieved[j] = False
return [2] + [pr for pr in sieved if sieved[pr]]
</code></pre>
<p>使用前1000000个整数作为我的范围,这段代码将生成正确数量的素数,并且只比我的基准慢3-5倍。我正要放弃,拍拍自己的背时,我尝试了一个更大的范围,但它不再工作!你知道吗</p>
<pre><code>n = 1,000 -- Benchmark = 168 in 0.00010 seconds
n = 1,000 -- Sieve3 = 168 in 0.00022 seconds
n = 4,194,304 -- Benchmark = 295,947 in 0.288 seconds
n = 4,194,304 -- Sieve3 = 295,947 in 1.443 seconds
n = 4,194,305 -- Benchmark = 295,947 in 3.154 seconds
n = 4,194,305 -- Sieve3 = 2,097,153 in 0.8465 seconds
</code></pre>
<p>我认为问题来自于<code>[****]</code>的行,但是我不明白为什么它会这么坏。它应该把“j”的每一个奇数倍都标记为假,而且大多数时候都是有效的,但是对于任何超过4194304的东西,这个筛子都是坏的。(公平地说,它也会在其他随机数字上中断,比如10000)。你知道吗</p>
<p>我做了一个更改,它大大减慢了我的代码速度,但它实际上适用于所有值。这个版本包括所有的数字(不仅仅是赔率),但在其他方面是相同的。你知道吗</p>
<pre><code>def sieve2(n):
top = n+1
sieved = dict.fromkeys(xrange(2,top), True)
for si in sieved:
if si * si > top:
break
if sieved[si]:
for j in xrange((si*2), top, si):
sieved[j] = False
return [pr for pr in sieved if sieved[pr]]
</code></pre>
<p>有人能帮我弄清楚为什么我原来的功能(sieve3)不能持续工作吗?你知道吗</p>
<p>编辑:我忘了提一下,当Sieve3“中断”时,Sieve3(n)返回n/2。你知道吗</p>