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

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列表的建立，它将提供更好的响应时间