Project1

标题: 教你快速判素数 [打印本页]
作者: yangff    时间: 2011-8-10 01:16
标题: 教你快速判素数
听完神犇的话后...
对干x<2^31-1我们有
x为素数当且仅当

a^x-1%x=1对a<21的正立整数成立
叫我是费马小定理
用二分快速幂，简单，有滋味。
作者: fux2    时间: 2011-8-10 01:19
喲！菲菲姐威武，前排學習。
作者: 做游戏的新手    时间: 2011-8-10 01:53
本帖最后由 做游戏的新手 于 2011-8-10 01:54 编辑

for i:=2 to trunc(Sqrt(x)) do if x mod i = 0 then exit(false)
特殊判断 if x<=1 then exit(false);
if x=2 then exit(true)
作者: 苏小脉    时间: 2011-8-10 03:53
本帖最后由 苏小脉 于 2011-8-10 03:59 编辑

Fermat 素性测试是非确定性的，它测的是拟素数，不是素数。从 Fermat 小定理的前件可以推出那个同余式，但它的逆命题却是假的。你只能说：如果你找到一个数 a 使得 a^(n-1) %n != 1 不同余，那么 n 就必然是合数。但如果反过来，就可能有合数 n 满足＂所有与 n 互质的整数 b 都满足 b^(n-1)%n = 1＂这个条件，这样的数被称为 Carmichael 数。

目前全世界最快的可用于所有自然数的确定性素性测试法是 AKS 素性测试，前几年被证明在 O(log6(n)) 时间内运行。有比它更快的测试，但要么就是非确定性的，要么就是有特定条件限制的。
作者: IamI    时间: 2011-8-10 09:05
本帖最后由 IamI 于 2011-8-10 09:15 编辑

这个费马小定理测出来的质数不是有反例的么……Matrix给出了2组“基本正确”的方法来着……
你信不信这货可以判定质数？
  1. /^1?$|^(11+?)\1+$/
复制代码
（先转二进制）
猛击我看上面这个诡异的正则原文
猛击我拆费马质数台
作者: SOU    时间: 2011-8-10 09:51
←_←虽然不明白但是觉得好厉害啊
我记得素数的判断是只能用筛选法的吧？
作者: 苏小脉    时间: 2011-8-10 09:55
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
我记得素数的判断是只能用筛选法的吧？ ...

通常在生成素数的列表的时候才用筛法，检测单个数的素性则另有多种（概率性的、确定性的）检测法，而不用把前面所有的素数都罗列出来。现今做研究的人找大质数通常都是用快速的概率性素性检测来找伪素数，然后再进行验证。
作者: 魔法教授    时间: 2011-8-10 11:33
那啥，你们在说啥……&素数是啥？
作者: yangff    时间: 2011-8-10 13:13
标题: 奥
本帖最后由 yangff 于 2011-8-10 13:15 编辑
苏小脉 发表于 2011-8-10 03:53
Fermat 素性测试是非确定性的，它测的是拟素数，不是素数。从 Fermat 小定理的前件可以推出那个同余式，但 ...


所以a从1~20可以使反例在2^31-1范围内不存在= =|我记得是这样？至少OI是没问题了
---------------------------------------------------------------------------------------------------------------------------------
log6N是骗人的AKS常数硕大无比，效率爆差2999...999977这伙敢跑3分钟……
---------------------------------------------------------------------------------------------------------------------------------
据说神犇用的都是Log10N的。
---------------------------------------------------------------------------------------------------------------------------------
据说ZJ有牛人出过线性筛能过，没优化的不能过的素数题
作者: 亿万星辰    时间: 2011-8-10 15:47
理论性太强，表示无法理解……
作者: 苏小脉    时间: 2011-8-11 03:12
所以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 06:39
本帖最后由 IamI 于 2011-8-11 06:40 编辑
苏小脉 发表于 2011-8-11 03:12 试试 399001 吧，一个 Carmichael 数。399001 = 31 x 61 x 211，你检查的 1~20 尽数与它互质，全都是 Ferm ...
OI竞赛，编辑满足题设要求的程序，限内存限时间，十组测试数据黑箱对比，结果正确给十分，超时不给分。他说的能过是指时间限制满足。
神牛=牛逼的人
作者: 小幽的马甲    时间: 2011-8-11 07:13
话说有谁在NOI现场……？NOI铜牌求虐



欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1