擅长:python、mysql、java
<pre><code>for n in xrange(i,limit,i):
a[n]=False
</code></pre>
<p>它应该是:</p>
^{pr2}$
<p>或者,更有效地:</p>
<pre><code>for n in xrange(i*i,limit, 2*i): #assuming you already cleared even numbers
a[n]=False
</code></pre>
<p>因为否则,当<code>i</code>实际上是一个素数时,就会将<code>i</code>设置为非素数。
(筛子应该将<code>i</code>的所有倍数标记为非素数,除了<code>i</code>本身!)在</p>
<hr/>
<p>请注意,您正在迭代所有的数字,直到<code>limit</code>,但是您可以在到达<code>sqrt(limit)</code>之后安全地停止:</p>
<pre><code>import itertools as it
def primesieve(limit):
a = [True] * limit
a[0] = a[1] = False
sqrt_limit = int(limit**0.5) + 1
predicate = lambda x: x[0] <= sqrt_limit
for i, isprime in it.takewhile(predicate, enumerate(a)):
if isprime:
for n in xrange(i*i, limit, i):
a[n] = False
return sum(i for i,n in enumerate(a) if n)
</code></pre>
<p><code>takewhile</code>函数将在到达<code>limit</code>的平方根后立即停止迭代。<code>i*i</code>不会出错,因为它总是小于<code>limit</code>。在</p>
<p>在我的机器上,它的速度是迭代所有数字的两倍。在</p>