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

傻眼貓咪

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

---

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

1. import time
   
2. 
   
3. def isPrime(n, k=5): # 米勒-拉宾质数判定法 Miller–Rabin Primality Test
   
4.     from random import randint
   
5.     if n < 2: return False
   
6.     for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]: # 小质数（50以内的质数作为范本）
   
7.         if not n%p: return n == p
   
8.     s, d = 0, n-1
   
9.     while not d%2:
   
10.         s, d = s+1, d>>1
    
11.     for i in range(k):
    
12.         x = pow(randint(2, n-1), d, n)
    
13.         if x == 1 or x == n-1: continue
    
14.         for r in range(1, s):
    
15.             x = (x * x) % n
    
16.             if x == 1: return False
    
17.             if x == n-1: break
    
18.         else: return False
    
19.     return True
    
20. 
    
21. arr = []
    
22. start_time = time.time()
    
23. for i in range(1000000):
    
24.     if isPrime(i):
    
25.         arr.append(i)
    
26. end_time = time.time() - start_time
    
27. print(f"共 {len(arr)} 个质数")
    
28. print("执行时间为：%s秒"%end_time)

复制代码

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

复制代码