作者Azraelx (胜败乃兵家之常事)
看板CSSE
标题Re: [问题] 检验质数？
时间Fri May 12 01:26:30 2006
※ 引述《shane123 (家产有八十七亿  ﰩ》之铭言：
: 请教各位一下
: 现今检验一个数是否为质数
: 最快的演算法是什麽？
: 它的 big-o 是多少呢？
: thanks la~~~
方法满多的
1.
要快速否定x是质数可以利用
if p is prime
a^p-1 = 1 mod p (忘了叫费马还尤拉了.XD 应该是费马小)
如果x是质数,就会满足
a^x-1 = 1 mod x, 如果不等,x就不是质数
2.
判断质数比较有名的有 MR-test, (miller-rabin test,不知道有没有拼错米勒XD)
不过印像中是机率式的判断法
3.
这几年有几篇文章,提出一个deterministic的方法可以在你给定一个x时,
回答你x是否为质数. 不过我没去看, 只是听老师上课提过.XD
能回答你的都只是这些概念性的问题...不好意思了...
如果有兴趣我可以再帮你细查 ^^
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.230.18.142
※ 编辑: Azraelx 来自: 61.230.18.142 (05/12 01:37)