为什么这个'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 seconds，所以是is_prime2(可能是+0.01s的平均差，也许正如我所说，全局变量的使用会破坏一些性能？)

Answer 1

区别在于三件事的结合：

1. 你只是没有做那么少的工作。您的测试用例包括测试大量的小数字；从2到平方根的所有数字"；以及测试"；从2到平方根的所有素数"；只是没什么区别。您的"；平均情况"；大约是范围的中点，50000，223.6的平方根，这意味着测试48个素数，或者如果数字是素数，则测试222个数字，但大多数数字不是素数，大部分数至少有一个小因子(证据留作练习)，因此，你短路了，实际上并没有测试任何一组中的大多数数字(如果有一个因子低于8，适用于所有数字的77%，你通过将自己限制在素数，节省了可能两个测试)

2. 你每次都在对mem进行切片，这是热切而完整的执行，即使你没有使用所有的值(正如所指出的，你几乎从来没有对非素数进行过切片)。这不是一个巨大的成本，但跳过非素数并没有带来巨大的节约，所以它可能会吃掉你从其他优化中获得的少量节约。

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

附带说明：

你的预先测试实际上并没有为你节省多少工作；你在循环中重做两个测试，所以当数字是素数时，它们是浪费精力的(你两次测试它们)。你的可被五整除性测试毫无意义；% 10并不比% 5快(计算机无论如何都不以10为基数运行)，而if not p % 5:是一种稍微更快、更直接、更完整的(你的测试不识别10的倍数，只有5的倍数不是10的倍数)测试可分割性的方法。

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

Answer 2

首先，您应该删除打印调用，这非常耗时。你应该只计时你的功能，而不是打印功能，所以你可以这样做：

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对我来说仍然更快。

Answer 3

如果您想在全局内存中保存素数以加速多次调用，则需要确保素数列表正确填充，即使使用随机顺序的数字调用函数也是如此。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    

在第一次调用未知素数时，它的执行速度将比除法方法慢，但随着素数列表的建立，它将提供更好的响应时间。