质数 - 米勒-拉宾质数判定法 Miller–Rabin Primality Test

傻眼貓咪

质数
米勒-拉宾质数判定法 Miller–Rabin Primality Test

---

计算 100万 (1,000,000)以内的所有质数，用时：1.911秒
代码：

import time

def isPrime(n, k=5): # 米勒-拉宾质数判定法 Miller–Rabin Primality Test
    from random import randint
    if n < 2: return False
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]: # 小质数（50以内的质数作为范本）
        if not n%p: return n == p
    s, d = 0, n-1
    while not d%2:
        s, d = s+1, d>>1
    for i in range(k):
        x = pow(randint(2, n-1), d, n)
        if x == 1 or x == n-1: continue
        for r in range(1, s):
            x = (x * x) % n
            if x == 1: return False
            if x == n-1: break
        else: return False
    return True

arr = []
start_time = time.time()
for i in range(1000000):
    if isPrime(i):
        arr.append(i)
end_time = time.time() - start_time
print(f"共 {len(arr)} 个质数")
print("执行时间为：%s秒"%end_time)

共 78498 个质数
执行时间为：1.9118878841400146秒