教你快速判素数

苏小脉

所以a从1~20可以使反例在2^31-1范围内不存在= =

试试 399001 吧，一个 Carmichael 数。399001 = 31 x 61 x 211，你检查的 1~20 尽数与它互质，全都是 Fermat liar。Fermat 素性测试通常都是每一步取伪随机的 Fermat base（也就是这里咱们提到的的 a），然后根据精确度的需求来决定迭代次数。

log6N是骗人的AKS常数硕大无比，效率爆差2999...999977这伙敢跑3分钟……

算法分析本来就和实现是两个层面的事物，有理想的算法，不一定有理想的实现。常量不会随数据复杂度增加而增加，你测小的数可能还没突破常量的界限，在测大数的时候 AKS 的优势就自然体现出来哉。

据说神犇用的都是Log10N的。

据说ZJ有牛人出过线性筛能过，没优化的不能过的素数题

不知所云 O_O
神犇 ＝？
ZJ ＝？
没优化的？？不能过？

IamI

苏小脉 发表于 2011-8-11 03:12 试试 399001 吧，一个 Carmichael 数。399001 = 31 x 61 x 211，你检查的 1~20 尽数与它互质，全都是 Ferm ...

OI竞赛，编辑满足题设要求的程序，限内存限时间，十组测试数据黑箱对比，结果正确给十分，超时不给分。他说的能过是指时间限制满足。
神牛=牛逼的人

小幽的马甲

话说有谁在NOI现场……？NOI铜牌求虐