擅长:python、mysql、java
<p>如注释中所述,您的函数过早返回True—例如,如果一个数字不能被2整除,并不意味着它不能被(2,n)范围内的任何后面的数字整除—请考虑51=3*17作为反例。你知道吗</p>
<p>以下是算法的正确版本:</p>
<pre><code>def isPrime(n):
if n > 1:
for i in range(2, n):
if n % i == 0:
return False
return True
else: # if we have a negative number or 0
return False
</code></pre>
<p>正如其他人提到的,有一种更快的方法来检查一个数是否是素数;现在您的函数的复杂度为<code>O(n)</code>,因为您检查的是n以内的所有数;通过观察<code>n = sqrt(n) * sqrt(n)</code>,检查到<code>sqrt(n) + 1</code>就足够了</p>
<pre><code>def isPrime(n):
if n > 1:
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
else:
return False
</code></pre>