python - 大整数素数检查算法

Question

我知道这是一个非常重复的问题，但我想了解我是否可以通过检查它是否可被 2、3、5 或 7 整除来简单地检查一个大整数（例如 157,632,829），或者我错过了角落案例？

IE。

if (n < 4) :
        return True
if (n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0) :
        return False

标签： pythonprimes

Answer 1

如果你不介意循环方法，那么你可以试试这个。在我的机器上运行 6 毫秒：

import math
import time

def gen_prime():
    D = {}
    q = 2
    while True:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        q += 1


def isprime(n):
    if n >= 2:
        g = gen_prime()
        s = int(math.sqrt(n))
        while True:
            d = next(g)
            if d > s:
                return True
            if n % d == 0:
                break
    return False

s = time.perf_counter()
r = isprime(157_632_829)
e = time.perf_counter()
print(f'{r} {e-s:.4f}s')

注意： gen_prime() 生成器不是我的。不幸的是，我不记得我从哪里得到它，所以不能给予信任