为了账号安全,请及时绑定邮箱和手机立即绑定

Python编程:筛法求两个数之间的素数

Python编程:筛法求两个数之间的素数

holdtom 2019-04-09 20:23:24
题目要求:PrimeGeneratorhttp://www.spoj.com/problems/PRIME1/要求计算最多10组,每组由两个数m,n构成(1

2 回答

?
九州编程

TA贡献1785条经验 获得超4个赞

筛法从时间复杂度上就没法满足题目的要求,超时是必然的。筛法求出小于sqrt(1000000000)的所有素数(大约3400个),然后用这些素数再筛一次来判断[m,n]之间的数是否是素数。
或者试试fermattest或者miller-rabintest吧因为是概率算法,会WA。
                            
查看完整回答
反对 回复 2019-04-09
  • 2 回答
  • 0 关注
  • 558 浏览
慕课专栏
更多

添加回答

代码语言

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信