python - 为什么我的第一个查找素数的函数比另一个函数花费的时间要长得多？

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
还有Prime -> 3, 5, 7, 9 , 11, 13, 15 , 17, 19
但是alsoPrime速度非常快 - 搜索前 1 000 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