为什么这个“优化”的主检查器运行速度与常规版本相同？

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 seconds，因此is_prime2（可能平均相差+0.01s，可能正如我所说的，使用全局变量会破坏一些性能？）

Answer 1

如果希望在全局内存中保留素数以加速多个调用，则需要确保正确填充素数列表，即使在以随机顺序调用函数时也是如此。is_prime2（）存储和使用素数的方法假设，例如，它在用343调用之前先用7调用。如果不是，343将被视为素数，因为7还不在素数列表中

所以函数必须计算并存储所有素数，直到√49才能响应is_prime（343）呼叫

为了快速建立素数表，埃拉托斯烯筛是最快的方法之一。但是，由于您事先不知道需要多少素数，因此无法预先分配筛选的位标志。你所能做的就是使用滚动的筛子窗口逐块向前移动（比如说一次1000000位）。当一个超过最大素数的数字被请求时，你只需逐块生成更多的素数，直到你有足够的响应为止

此外，由于您要构建一个素数列表，您不妨将其设置为一个集合，并检查请求的数字是否在其中以响应函数调用。这将需要生成比除法所需的素数更多的素数，但出于加速后续调用的精神，这不应该是一个问题

下面是使用该方法的isPrime（）函数的示例：

primes      = {3}
sieveMax    = 3
sieveChunk  = 1000000 # must be an even number
def isPrime(n):
    if not n&1: return n==2
    global primes,sieveMax, sieveChunk
    while n>sieveMax:
        base,sieveMax = sieveMax, sieveMax + sieveChunk
        sieve = [True]* sieveChunk
        for p in primes:
            i = (p - base%p)%p
            sieve[i::p]=[False]*len(sieve[i::p])
        for i in range(0, sieveChunk,2):
            if not sieve[i]: continue
            p = i + base
            primes.add(p)
            sieve[i::p] = [False]*len(sieve[i::p])
    return n in primes    

在第一次调用未知的prime时，它将比divisions方法执行得慢，但随着prime列表的建立，它将提供更好的响应时间

Answer 2

区别在于三个方面的结合：

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

2. 每次都要对mem进行切片，即使没有使用所有的值（如前所述，对于非素数，您几乎从来没有使用过），也会急切地、完整地执行该操作。这并不是一个巨大的成本，但是，跳过非素数并没有带来巨大的节约，因此它可能会吃掉从其他优化中获得的少量节约

3. （你发现了这一个，很好的展示）你的素数切片需要测试的素数的个数等于要测试的素数的平方根，而不是所有的素数都小于要测试的素数的平方根。因此，实际上您执行了相同数量的测试，只是使用了不同的数字（其中许多素数大于平方根，绝对不需要测试）

旁注：

你的前期测试实际上并没有为你节省很多工作；您在循环中重复这两个测试，因此当数字为素数时，这两个测试都是徒劳的（您测试了两次）。你对5的可除性的测试是毫无意义的% 10比% 5快不了多少（计算机无论如何都不以10为基数运行），而if not p % 5:是一种更快、更直接、更完整的测试方法（您的测试不识别10的倍数，只是5的倍数，不是10的倍数）

这些测试也是错误的，因为它们不排除基本情况（它们说2和5不是素数，因为它们分别可被2和5整除）

Answer 3

首先，您应该删除打印调用，这非常耗时。 您应该只对函数计时，而不是打印函数，因此您可以这样做：

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
    is_prime1(p)
end = time.perf_counter()

print ("prime1", end-start)


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
    is_prime2(p)
end = time.perf_counter()

print ("prime2", end-start)

is_prime1对我来说更快