求解一道算法题!
算法吧
全部回复
仅看楼主
level 1
已知狄利克雷定理:a,b为素数,n为正整数,那么有无数多的形式an+b
问题是,输入a,b,m,输出an+b中得到的第m个质数
想了很久时间复杂度也降不下去啊
2018年12月22日 13点12分 1
level 7
题目的规模应该很小吧,应该是直接枚举,然后用米勒罗宾测试就行了吧。
如果这样复杂度还高的话,可以用类似筛的办法筛掉一些候选数。比如你考察a%2,a%3,a%5...的余数,可以筛掉一些不可能的n。但我估计不用筛,直接枚举就行了。
2018年12月23日 05点12分 2
不太小。。a b是不大于1e8 m不大于1e3
2018年12月23日 05点12分
完全够了,一直枚举测出m个素数就行了
2018年12月24日 05点12分
1