如何加速验证素数的 python 程序？

Question

我编写了这个简单的 python 3.7 代码来验证素数，但是我发现长度超过 10 位的数字存在瓶颈。我知道这很薄弱，但我认为在您的帮助下这段代码是有希望的。

是否可以加速这个程序，使其运行超快？

程序声明复合数为 False，素数为 True。例如这个数字 (1235468711) 需要 16 秒才能报告 False 等于一个合数。

顺便说一句，(a) 必须保持该状态才能使代码正常工作。

我试过压缩映射，没有发现速度提升。

代码如下：

p = int(input('Enter a prime number and if True its prime: '))

def prime(*kwargs):
    for i in kwargs:
        yield i 
k = (2 * p)

a = prime((2 ** (p + 1) - 1) % k)

for i in a:
    if i == 3:
        print(i is not False, "| If True number is prime!")
    else:
        print(False, "| If False number is not prime!")

Answer 1

此伪素数素性测试的问题在于：

a = prime(((2**(((((p+1)))))-1))%k)

因为它需要计算一个昂贵的幂，然后才取它的模数。

然而，Python 确实提供了 pow()，它可以比 pow(a, b, c).

更有效地计算 a ** b % c

在你的情况下，这与你周围有一个额外的 -1 的公式不完全相同。由于 (a ** b - 1) % c 通常不同于 a ** b % c - 1，您需要一些额外的计算来重现完全相同的公式。例如，您可以使用额外的 if 即：

x = pow(a, b, c)
x += -1 if x > 0 else c - 1

或添加额外的模运算：

(pow(a, b, c) - 1) % c

为了给你一些基准，我在我的机器上观察到建议的方法有 +200 倍的加速：

p = 123456

print(((2**(((((p+1)))))-1))%(2 * p))
# 127999
print((pow(2, p + 1, 2 * p) - 1) % (2 * p))
# 127999

%timeit ((2**(((((p+1)))))-1))%(2 * p)
# 1000 loops, best of 3: 466 µs per loop
%timeit (pow(2, p + 1, 2 * p) - 1) % (2 * p)
# 1000000 loops, best of 3: 1.75 µs per loop

请注意，周围有更高效的(pseudo-)primality tests。

如何加速验证素数的 python 程序？

How to speed up a python program which verifies prime numbers?

python-3.x

calculation