运行时优化是否为Prime

Question

我的任务是编写一个以整数形式输入的程序。如果该数是素数，则程序返回1;如果该数不是素数，则程序返回大于1的最小除数。

def isPrime(n):
if n > 1:
for i in range (2,n):
if (n % i) == 0 :
return i 
return 1 

我正在努力改善这段代码的运行时间，我可以得到一些帮助吗?

Answer 1

使用相同的算法，您可以采取的改善运行时的一个步骤是优化for循环，以便它只检查n的平方根:

def isPrime(n):
if n > 1:
for i in range (2,int(n ** .5) + 1):
if (n % i) == 0 :
return i 
return 1 

这将把你的算法的运行时间从O(n)减少到O(sqrt(n))

好吧，既然你要求解释为什么我们只检查n的平方根:

假设我们有一个数字，36。36的因子为:1,2,3,4,6,9,12,18,36

在任何情况下，如果36的因数是a和b，那么a * b = 36和a < b，这个不等式将永远成立:

a <= sqrt(36) <= b

这意味着，如果从2一直到根号n没有36的因数，则不存在大于根号n的因数。

我们也检查平方根的原因是对于像49这样的数字，除了平方根7之外没有其他因子。这就是为什么我们给int(n ** .5)加1，因为转换会将其舍入，这使得它不包含在for循环中。