教你快速判素数

yangff

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

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

fux2

喲！菲菲姐威武，前排學習。

做游戏的新手

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)

苏小脉

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

目前全世界最快的可用于所有自然数的确定性素性测试法是 AKS 素性测试，前几年被证明在 O(log6(n)) 时间内运行。有比它更快的测试，但要么就是非确定性的，要么就是有特定条件限制的。

IamI

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

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

复制代码

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

SOU

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

苏小脉

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
我记得素数的判断是只能用筛选法的吧？ ...

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

魔法教授

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

yangff

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

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

亿万星辰

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