检查给定的大数是否为素数的最快方法是什么?我说的是大小约为 10^32 的数字。我已经尝试过该算法@MarcoBonelli 的精彩回答 https://stackoverflow.com/a/27946768/1195131这是:
from math import sqrt; from itertools import count, islice
def isPrime(n):
return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))
但它给出了错误Stop argument for islice() must be None or an integer: 0 <= x <= sys.maxsize
当针对如此大的数字使用时。那么有什么不同的、快速的方法呢?
这是我对 Miller-Rabin 素性测试的实现;它默认为 5 次随机试验,但您可以根据需要进行调整。循环开启p是小素数的快速回归。
def isPrime(n, k=5): # miller-rabin
from random import randint
if n < 2: return False
for p in [2,3,5,7,11,13,17,19,23,29]:
if n % p == 0: return n == p
s, d = 0, n-1
while d % 2 == 0:
s, d = s+1, d/2
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
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)