Python素数检测的方法
5星 · 超过95%的资源 163 浏览量
2020-12-25
02:14:07
上传
评论
收藏 52KB PDF 举报 
Python素数检测的方法素数检测的方法
本文实例讲述了Python素数检测的方法。分享给大家供大家参考。具体如下：
因子检测：因子检测：
检测因子，时间复杂度O(n^(1/2))
def is_prime(n):
if n < 2:
return False
for i in xrange(2, int(n**0.5+1)):
if n%i == 0:
return False
return True
费马小定理：费马小定理：
如果n是一个素数，a是小于n的任意正整数，那么a的n次方与a模n同余
实现方法：
选择一个底数（例如2），对于大整数p，如果2^(p-1)与1不是模p同余数，则p一定不是素数；否则，则p很可能是一个素数
2**(n-1)%n 不是一个容易计算的数字
模运算规则：
(a^b) % p = ((a % p)^b) % p
(a * b) % p = (a % p * b % p) % p
计算X^N(% P)
可以
如果N是偶数，那么X^N =（X*X）^[N/2]；
如果N是奇数，那么X^N = X*X^(N-1) = X *（X*X）^[N/2]；
def xn_mod_p(x, n, p):
if n == 0:
return 1
res = xn_mod_p((x*x)%p, n>>1, p)
if n&1 != 0:
res = (res*x)%p
return res
也可以归纳为下面的算法 两个函数是一样的
def xn_mod_p2(x, n, p):
res = 1
n_bin = bin(n)[2:] for i in range(0, len(n_bin)):
res = res**2 % p
if n_bin[i] == '1':
res = res * x % p
return res
有了模幂运算快速处理就可以实现费马检测
费马测试当给出否定结论时，是准确的，但是肯定结论有可能是错误的，对于大整数的效率很高，并且误判率随着整数的增大
而降低
def fermat_test_prime(n):
if n == 1:
return False
if n == 2:
return True
res = xn_mod_p(2, n-1, n)
return res == 1
MILLER-RABIN检测检测
Miller-Rabin检测是目前应用比较广泛的一种
- 1
- 2
前往页