我可以用这种方法写一个质数的函数
def isprime(num):
if num > 1:
for i in range(2, num):
if num % i == 0:
return False
return True
%timeit [i for i in range(1000) if isprime(i)]
7.94 ms ± 273 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)然后我发现有一种更快的方法，用平方根来写这个，但我不明白它的工作原理。有人能用更简单的语言解释一下这段代码吗？为什么它能工作？
def isprime(num):
if num > 1:
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
%timeit [i for i in range(1000) if isprime(i)]
1.94 ms ± 54.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)如果这是一个重复，请让我知道我会立即删除它。
3条答案
按热度按时间kqqjbcuj1#
这是最好的解释的例子。假设你想知道143是否是质数。你真的需要试着除以142、141、140、139等等吗？显然，这些都不能整除143;太大了。
但请看：
显然，11能除143。不是质数。
现在试试145. 145是质数吗
显然，5能除145。不是质数。现在想想，我们可以尝试
这本来是可行的，因为145 = 529，但没有必要尝试一个大到29的因子。五个就够了。
想想看。如果一个合数n = ab有两个因子a和b，假设b > sqrt（n）。在这种情况下，一定是a < sqrt（n）的情况，因为如果不是这样，那么ab就不可能等于n。事实上，如果不是这样，那么aB将 * 大于 * n，这意味着a*B不是n的适当因式分解。
你所要做的就是找出最小因子的值。较小的因子小于或至多等于平方根。如果没有发现小于或等于平方根的因子，那么所研究的数就是素数。
raogr8fs2#
你只需要检查一个数的平方根的因子，以确定这个数是否是质数--任何大于它的平方根的因子都必须与小于它的平方根的一个因子配对，你已经检查过了。
这允许第二个实现更早地完成它的循环（例如，你只需要测试2..31来确定997是质数，而不是像第一个实现中那样测试2..996）。
wixjitnu3#
即使这个代码也提出了同样的问题，这里25应该是非质数，但它是质数。