Re: [問題] 檢驗質數？
※ 引述《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)
討論串 (同標題文章)