擅长:python、mysql、java
<p>首先,你具体问题的答案。你正在丢弃小于<em>n</em>平方根的素数。最简单的修复方法是在内部循环的末尾将<code>num[i] = False</code>更改为<code>num[i] = (not x == i)</code>(我认为这是可行的,我还没有测试过)。在</p>
<p>第二,你的算法是试除法,而不是埃拉托什尼的筛子,它的时间复杂度是O(n2)而不是O(logloglogn)。模运算符给出了博弈结果。最简单的Eratosthenes筛选如下(伪代码,可以将其翻译为Python):</p>
<pre><code>function primes(n)
sieve := makeArray(2..n, True)
for p from 2 to n step 1
output p
for i from p+p to n step p
sieve[i] := False
</code></pre>
<p>有一些方法可以改进这种算法。如果您对使用质数编程感兴趣,我谦虚地推荐<a href="http://programmingpraxis.com/essays" rel="nofollow">this essay</a>,它包括一个优化的Eratosthenes筛选,并用Python实现。在</p>