Python素数检测的方法
作者：蛇小狼
字体：[ ] 类型：转载 时间：
这篇文章主要介绍了Python素数检测的方法,实例分析了Python素数检测的相关技巧,需要的朋友可以参考下
本文实例讲述了Python素数检测的方法。分享给大家供大家参考。具体如下：
因子检测：
检测因子，时间复杂度O(n^(1/2))
def is_prime(n):
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:
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):
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检测是目前应用比较广泛的一种
二次探测定理:如果p是一个素数,且0&x&p,则方程x^2%p=1的解为:x=1或x=p-1
费马小定理：a^(p-1) ≡ 1(mod p)
这就是Miller-Rabin素性测试的方法。不断地提取指数n-1中的因子2，把n-1表示成d*2^r（其中d是一个奇数）。那么我们需要计算的东西就变成了a的d*2^r次方除以n的余数。于是，a^(d * 2^(r-1))要么等于1，要么等于n-1。如果a^(d * 2^(r-1))等于1，定理继续适用于a^(d * 2^(r-2))，这样不断开方开下去，直到对于某个i满足a^(d * 2^i) mod n = n-1或者最后指数中的2用完了得到的a^d mod n=1或n-1。这样，Fermat小定理加强为如下形式：
尽可能提取因子2，把n-1表示成d*2^r，如果n是一个素数，那么或者a^d mod n=1，或者存在某个i使得a^(d*2^i) mod n=n-1 ( 0&=i&r ) （注意i可以等于0，这就把a^d mod n=n-1的情况统一到后面去了）
定理:若n是素数,a是小于n的正整数,则n对以a为基的Miller测试,结果为真.
Miller测试进行k次,将合数当成素数处理的错误概率最多不会超过4^(-k)
def miller_rabin_witness(a, p):
if p == 1:
return False
if p == 2:
return True
#p-1 = u*2^t 求解 u, t
t = int(math.floor(math.log(n, 2)))
while t & 0:
u = n / 2**t
if n % 2**t == 0 and u % 2 == 1:
b1 = b2 = xn_mod_p2(a, u, p)
for i in range(1, t + 1):
b2 = b1**2 % p
if b2 == 1 and b1 != 1 and b1 != (p - 1):
return False
if b1 != 1:
return False
return True
def prime_test_miller_rabin(p, k):
while k & 0:
a = randint(1, p - 1)
if not miller_rabin_witness(a, p):
return False
return True
希望本文所述对大家的Python程序设计有所帮助。
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。
问题对人有帮助，内容完整，我也想知道答案
问题没有实际价值，缺少关键内容，没有改进余地
from math import sqrt
def isprime(x):
if x == 1:
return False
k = int(sqrt(x))
for i in range(2,k+1):
if x % i == 0:
return False
return True
for j in range(2,101):
if isprime(j):
结果如图：
看不懂问题出在哪里，为啥不能输出素数呢？谢谢！
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
for i in range(2,k+1):
if x % i == 0:
return False
return True
当x%i != 0时 判断第一次就return了
应该 x%i == 0 时return 然后如果这里没return就应该到for执行完后再return
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
for i in range(2,k+1):
if x % i == 0:
return False
return True
你仔细看看这里逻辑能对吗，需要一直循环处理才行，这里只是判断一次是true还是false了，还怎么能判断素数？
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
最后一个return拿到外面，不然在i=2的时候就必须做一个返回了
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
from math import sqrt
def isprime(x):
if x == 1:
return False
k = int(sqrt(x))
for i in range(2,k+1):
if x % i == 0:
return False
return True
for j in range(2,101):
if isprime(j):
同步到新浪微博
分享到微博？
关闭理由：
删除理由：
忽略理由：
推广（招聘、广告、SEO 等）方面的内容
与已有问题重复（请编辑该提问指向已有相同问题）
答非所问，不符合答题要求
宜作评论而非答案
带有人身攻击、辱骂、仇恨等违反条款的内容
无法获得确切结果的问题
非开发直接相关的问题
非技术提问的讨论型问题
其他原因（请补充说明）
我要该，理由是：
在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。Python编程#输出n以内的所有质数。_百度知道
Python编程#输出n以内的所有质数。
代码我是这样写的
n = int(input('Please input n:'))
for i in range(2,n):
for j in range(2,i):
if i%j==0:
num.append(i)
print(num)
输出的结果是：
我有更好的答案
不能被其他自然数整除的数。一般正常人的解法是两次循环，假设求小于N的所有素数。一次用N-1之间的所有数去除。指在一个大于1的自然数中，除了1和此整数自身外。否则是素数，如果能被整除这个数肯定不是素数质数又称素数
少了一对括号：if i%j==0: 改为if(i%j==0):
else应该很for对应
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。python中如何编程求1到100之间的素数_百度知道
python中如何编程求1到100之间的素数
def&primes(x):&&&&#&prepair&data&space&&&&plist&=&[0,&0]&+&range(2,x+1)&&&&for&i&in&xrange(2,&x):&&&&&&&&if&plist[i]:&&&&&&&&&&&&plist[i+i::i]&=&[0]&*&len(plist[i+i::i])&&&&return&filter(None,&plist)print&primes(100)筛选法是高效的素数列表计算算法, python的列表切片赋值可以极大地简化代码
采纳率：63%
来自团队：
79,&83!/usr/bin/python27#&nbsp,&37,&41,&100以内的质数(素数)'&#39,&nbsp,&not&in&[n%i&for&nbsp:
l;71,&73;'l&2,&nbsp:[2,&3,&5,&7,&11,&61,&67;13,&17:
continue elif&n&i&in&range(2,n)]:
l;53,&59,&nbsp,&nbsp.append(2) else:
if&0&43,&47,&l运行结果;coding:utf8'29,&31.append(n)print&19,&23;==&1;n&in&range(1,101);==&nbsp: if&n&=&[]for&'&#39#,&nbsp
本回答被提问者采纳
你要不要考虑效率了，这笨办法也不慢，100以为的话，不考虑效率最简单的就是双层循环试呗
我试了，可出问题，能帮我弄下吗😊
它输出时，一个数要输出好多遍，为什么啊
可以发上你的代码嘛，我帮你看看
本回答被网友采纳
&in&for&p&range(2;101)&for&d&in&range(2,&in&if&0&not&[p%&d&nbsp[p&nbsp
其他1条回答
为您推荐：
其他类似问题
您可能关注的内容
python的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。动脑时间-一个数学问题，用python代码实现-判断素数动脑时间-一个数学问题，用python代码实现-判断素数运维菜百家号前言今天一个当老师的同学问我判断一个数是不是素数？用代码怎么实现？突然懵了，素数是什么？质数质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。那要怎么判断呢？是不是一个个除判断是否有余数？是不是还有更简单的方法？假设n不是素数，那应该有n=a*b（a、b、n都是正整数，且n&a&1和n&b&1），那么根号n和a、b有什么关系呢？由不是素数的等式n=a*b，可以出现两种情况：1、如果a=b=根号n，那么我只要判断n除以根号n，余数为0,就可以认为它不是素数。2、如果a&根号n且b&根号n，那么a*b & 根号n × 根号n =n，这种情况是一定不存在的，因为我们的前提是n不是素数n=a*b。因此可以判断a和b中，至少要有一个小于根号n。总结因此判断一个正整数n是不是素数，只要n跟2到根号n取余，如果出现0，说明可以除尽，存在因数，就可以证明它不是素数。代码实现本文仅代表作者观点，不代表百度立场。系作者授权百家号发表，未经许可不得转载。运维菜百家号最近更新：简介:运维一点点积累、分享作者最新文章相关文章