教你快速判素数

yangff

听完神犇的话后...
对干x<2^31-1我们有
x为素数当且仅当

a^x-1%x=1对a<21的正立整数成立
叫我是费马小定理
用二分快速幂，简单，有滋味。

小幽的马甲

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

IamI

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

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

苏小脉

所以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 ＝？
没优化的？？不能过？

亿万星辰

理论性太强，表示无法理解……

yangff

苏小脉 发表于 2011-8-10 03:53
Fermat 素性测试是非确定性的，它测的是拟素数，不是素数。从 Fermat 小定理的前件可以推出那个同余式，但 ...

所以a从1~20可以使反例在2^31-1范围内不存在= =|我记得是这样？至少OI是没问题了
---------------------------------------------------------------------------------------------------------------------------------
log6N是骗人的AKS常数硕大无比，效率爆差2999...999977这伙敢跑3分钟……
---------------------------------------------------------------------------------------------------------------------------------
据说神犇用的都是Log10N的。
---------------------------------------------------------------------------------------------------------------------------------
据说ZJ有牛人出过线性筛能过，没优化的不能过的素数题

魔法教授

那啥，你们在说啥……&素数是啥？

苏小脉

IamI 发表于 2011-8-10 09:05
这个费马小定理测出来的质数不是有反例的么……Matrix给出了2组“基本正确”的方法来着……
你信不信这货可 ...

那个不是二进制，是把 n 变为 n 个 "1" 串联后的字串 -v-

Miller–Rabin 素性测试原是非确定性的，后来在其基础上又演变出了确定性的变异版，只是算法依赖于至今仍未能证明或反证的  Riemann （黎曼）猜想。


苏小脉于2011-8-10 10:01补充以下内容：

SOU 发表于 2011-8-10 09:51
我记得素数的判断是只能用筛选法的吧？ ...

通常在生成素数的列表的时候才用筛法，检测单个数的素性则另有多种（概率性的、确定性的）检测法，而不用把前面所有的素数都罗列出来。现今做研究的人找大质数通常都是用快速的概率性素性检测来找伪素数，然后再进行验证。

SOU

←_←虽然不明白但是觉得好厉害啊
我记得素数的判断是只能用筛选法的吧？

IamI

这个费马小定理测出来的质数不是有反例的么……Matrix给出了2组“基本正确”的方法来着……
你信不信这货可以判定质数？

1. /^1?$|^(11+?)\1+$/

复制代码

（先转二进制）
猛击我看上面这个诡异的正则原文
猛击我拆费马质数台