擅长:python、mysql、java
<p>堆栈上重复调用太多可能会导致堆栈溢出。在42751,您将有一个21375深度函数调用堆栈。在这种情况下,实际上可能需要改进您的方法。在</p>
<p>一个检查素数的简单例程可以这样写(伪代码):</p>
<pre><code>if n < 2 return false;
if n == 2 or n == 3 return true;
if n % 2 == 0 return false;
if n % 3 == 0 return false;
for (i = 6; i < sqrt(n); i += 6) {
if (n % (i - 1) == 0) return false;
if (n % (i + 1) == 0) return false;
}
return true;
</code></pre>
<p>这种方法之所以有效,是因为:</p>
<ol>
<li>如果n小于2,它就不可能是素数</li>
<li>如果n是2或3,它必须是素数</li>
<li>如果n不是2或3,但可以被其中一个整除,则它不是素数</li>
<li>除了2和3以外的所有质数都可以写成6k+1或6k-1。如果一个数是素数,它就不能被其他素数整除。只需要检查n的平方根,因为任何超过这个数的东西肯定不能被平均分为n</li>
</ol>