质数 - 米勒-拉宾质数判定法 Miller–Rabin Primality Test
本帖最后由 傻眼貓咪 于 2021-10-12 19:18 编辑质数
米勒-拉宾质数判定法 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 : # 小质数（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秒
页:
[1]