为什么我的第一个函数查找素数的时间比另一个长得多

Question

我有两个函数：isPrime和alsoPrime。如果数字(x(是素数，则两者都意味着返回True或False。isPrime(x, pLis)采用素数的增长列表，并观察x是否是任何素数的倍数。alsoPrime(x)搜索所有从3开始、到x的根的奇数。然后我使用for循环，从3开始，以2的间隔递增。

我预计isPrime会更快，因为它应该跳过数字，即：

isPrime->3、5、7、11、13、17、19

alsoPrime->3、5、7、9、11、13、15，17、19

但alsoPrime的速度要快得多，在搜索前1000 000个数字时要快100倍。

有人能解释一下原因吗？每次呼叫pLis都要花很多时间吗

def isPrime(x, pLis):
for item in pLis:
if x % item == 0:
return False
return True

def alsoPrime(x):
for i in range(3, round(x**0.5)+1, 2):
if x % i == 0:
return False
return True

Answer 1

您正在遍历在isPrime中发现的所有素数，而实际上只需要遍历到候选素数的平方，就像在alsoPrime中一样。迭代次数越多，代码就越慢。验证这一点的快速方法是计算迭代次数，如下所示：

def isPrime(x, pLis):
for i, item in enumerate(pLis):
if x % item == 0:
print(f"{x} is not prime after {i} iterations")
return False
print(f"{x} is prime after {i} iterations")
return True