擅长:python、mysql、java
<p>穷举除法直到平方根是你能想到的最简单的。最坏的情况是对于素数,因为所有的除法都必须执行。无论如何,直到十亿年,几乎没有可测量的时间(约1.2ms)。</p>
<pre><code>def Prime(n):
if n & 1 == 0:
return 2
d= 3
while d * d <= n:
if n % d == 0:
return d
d= d + 2
return 0
</code></pre>
<p>请注意,此版本返回的是最小除数或<code>0</code>,而不是布尔值。</p>
<p>有些微优化是可能的(比如使用一个增量表),但我不认为它们能产生很大的收益。</p>
<p>有更复杂和更快的方法可用,但我不确定它们是否值得为这么小的<code>n</code>而大惊小怪。</p>