<p>以下是我对这个问题的看法:</p>
<pre><code>from math import sqrt; from itertools import count, islice
def isPrime(n):
return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))
</code></pre>
<p>这是一个非常简单和简洁的算法,因此它并不意味着任何接近最快或最优化的素性检查算法。它的时间复杂度为<code>O(sqrt(n))</code>。<strong>继续<a href="http://primes.utm.edu/prove/index.html" rel="noreferrer">here</a>学习更多关于正确完成的素性测试及其历史的知识。</p>
<hr/>
<h2>解释</h2>
<p>我会告诉你一些关于几乎深奥的一行代码的内幕,这些代码将检查素数:</p>
<ul>
<li><p>首先,使用<code>range()</code>确实是个坏主意,因为它将创建一个数字列表,这将使用大量内存。使用<code>xrange()</code>更好,因为它创建了一个<em>生成器</em>,它只需要记住您提供的初始参数,并动态生成每个数字。如果你在使用
Python 3或更高版本<code>range()</code>已默认转换为生成器。顺便说一句,这根本不是最好的解决方案:尝试为某些<code>n</code>调用<code>xrange(n)</code>,这样<code>n > 2<sup>31</sup>-1</code>(这是C<code>long</code>的最大值)会提高<code>OverflowError</code>。因此,创建范围生成器的最佳方法是使用<code>itertools</code></strong>:</p>
<pre><code>xrange(2147483647+1) # OverflowError
from itertools import count, islice
count(1) # Count from 1 to infinity with step=+1
islice(count(1), 2147483648) # Count from 1 to 2^31 with step=+1
islice(count(1, 3), 2147483648) # Count from 1 to 3*2^31 with step=+3
</code></pre></li>
<li><p><strong>如果要检查<code>n</code>是否是质数,实际上不需要一直到<code>n</code></strong>为止。您可以显著地减少测试,并且只检查从2到<code>√(n)</code>(平方根<code>n</code>)。下面是一个例子:</p>
<p>让我们找出<code>n = 100</code>的所有除数,并将它们列在表中:</p>
<pre class="lang-none prettyprint-override"><code> 2 x 50 = 100
4 x 25 = 100
5 x 20 = 100
10 x 10 = 100 <-- sqrt(100)
20 x 5 = 100
25 x 4 = 100
50 x 2 = 100
</code></pre>
<p>你很容易就会注意到,<strong>在<code>n</code>的平方根之后,我们找到的所有除数实际上都已经找到了。例如,在执行<code>100/5</code>操作时已找到<code>20</code>。一个数的平方根是我们发现的除数开始重复的确切中点。因此,<strong>要检查一个数是否是素数,只需要检查2到<code>sqrt(n)</code></strong>。</p></li>
<li><p>那为什么是<code>sqrt(n)-1</code>,而不仅仅是<code>sqrt(n)</code>?这是因为提供给<code>itertools.islice</code>对象的第二个参数是要执行的迭代次数。<strong><code>islice(count(a), b)</code>在迭代后停止。这就是为什么:</p>
<pre><code>for number in islice(count(10), 2):
print number,
# Will print: 10 11
for number in islice(count(1, 3), 10):
print number,
# Will print: 1 4 7 10 13 16 19 22 25 28
</code></pre></li>
<li><p>函数<code>all(...)</code>与以下相同:</p>
<pre><code>def all(iterable):
for element in iterable:
if not element:
return False
return True
</code></pre>
<p>它逐字地检查<code>iterable</code>中的所有数字,当一个数字的计算结果为<code>False</code></strong>时返回<code>False</code>(这意味着仅当数字为零时)。那我们为什么要用它呢?首先,我们不需要使用额外的索引变量(就像我们使用循环一样),除此之外:为了简洁起见,实际上并不需要它,但是只使用一行代码而不是多行嵌套代码看起来就不那么庞大了。</p></li>
</ul>
<h2>扩展版本</h2>
<p>我包括一个<code>isPrime()</code>函数的“解包”版本,以便更容易理解和阅读:</p>
<pre><code>from math import sqrt
from itertools import count, islice
def isPrime(n):
if n < 2:
return False
for number in islice(count(2), int(sqrt(n) - 1)):
if n % number == 0:
return False
return True
</code></pre>