python - 为什么这个 'optimized'素数检查器的运行速度与普通版本相同？

Question

鉴于这个简单的 is_prime1 函数，它通过一些位操作检查从 1 到 sqrt(p) 的所有除数，以避免偶数当然不是素数。

import time
def is_prime1(p):
    if p & 1 == 0:
        return False
    # if the LSD is 5 then it is divisible by 5 (i.e. not a prime)
    elif p % 10 == 5:
        return False

    for k in range(2, int(p ** 0.5) + 1):
        if p % k == 0:
            return False
    return True

与此“优化”版本相比。这个想法是保存我们找到的所有素数，直到某个数字 p，然后我们迭代这些素数(使用这个基本算术规则，每个数字都是素数的乘积)，所以我们不会迭代这些数字，直到 sqrt( p) 但在素数上我们发现与 sqrt(p) 相比应该很小。我们还只迭代一半的元素，因为这样最大的素数肯定不会“适合”数字 p。

import time
global mem
global lenMem
mem = [2]
lenMem = 1

def is_prime2(p):
    global mem
    global lenMem
    # if p is even then the LSD is off

    if p & 1 == 0:
        return False
    # if the LSD is 5 then it is divisible by 5 (i.e. not a prime)
    elif p % 10 == 5:
        return False

    for div in mem[0: int(p ** 0.5) + 1]:
        if p % div == 0:
            return False
    mem.append(p)
    lenMem += 1
    return True

我唯一的想法是“全局变量既昂贵又耗时”，但我不知道是否还有其他方法，如果有的话，它真的有帮助吗？

平均而言，运行同一程序时:

start = time.perf_counter()
for p in range(2, 100000):
    print(f'{p} is a prime? {is_prime2(p)}') # change to is_prime1 or is_prime2
end = time.perf_counter()

我知道，对于 is_prime1，检查数字 1-100K 的平均时间是 ~0.99 秒，所以 is_prime2 (可能有区别平均+0.01s，也许正如我所说，全局变量的使用会破坏一些性能？)

Answer 1

差异在于以下三点的结合:

1. 你所做的工作并没有减少那么多。您的测试用例包括测试大量小数字，其中测试“从 2 到平方根的所有数字”和测试“从 2 到平方根的所有素数”之间的区别并没有那么大。您的“平均情况”大约是范围的中点，50,000，223.6 的平方根，这意味着测试 48 个素数，或者测试 222 个数字(如果数字是素数，但大多数数字不是素数) ，并且大多数数字至少有一个小因子(证明留作练习)，因此您可以短路并且实际上不会测试任一组中的大多数数字(如果有一个因子低于 8，这适用于约 77% 的数字，通过将自己限制为素数，您也许节省了两次测试)

2. 您每次都会对 mem 进行切片，即使您没有使用所有值(正如所指出的，您几乎从不这样做)，这也是急切且完整地执行的非素数)。这并不是一个巨大的成本，但是，您并没有从跳过非素数中获得巨大的节省，因此它可能会消耗您从其他优化中获得的少量节省。

3. (你找到了这个，很好的表演)你的素数切片需要测试数字个素数，这些素数等于要测试的数字的平方根，而不是所有素数都小于平方根要测试的数字的根。因此，您实际上执行了相同数量的测试，只是使用了不同的数字(其中许多素数大于平方根，绝对不需要测试)。

旁注:

您的前期测试实际上并没有为您节省太多工作；您在循环中重做这两个测试，因此当数字为素数时，它们就浪费了精力(您对它们都进行了两次测试)。你对能被五整除的测试是毫无意义的； % 10 并不比 % 5 快(计算机无论如何都不会以 10 为基数运行)，并且 if not p % 5: 是一种稍微更快、更直接、更完整(您的测试无法识别 10 的倍数，只能识别不是 10 的倍数的 5 的倍数)的整除性测试方法。

测试也是错误的，因为它们没有排除基本情况(它们说 2 和 5 不是素数，因为它们分别能被 2 和 5 整除)。