※ 引述《Azraelx (勝敗乃兵家之常事)》之銘言： : ※ 引述《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就不是質數 補充一點 如果=1不一定是質數喔 而且還有Carmichael number這種怪胎.... (Carmichael number就是: 若一個x 對所有小於x的正整數a a^(x-1) = 1 mod x 但x卻不是質數 它就被稱做Carmichael number 印象中最小的是561) 所以此法只用來否定質數性 不能用來肯定質數性 : 2. : 判斷質數比較有名的有 MR-test, (miller-rabin test,不知道有沒有拼錯米勒XD) : 不過印像中是機率式的判斷法 是機率式的沒錯 其他機率式的判斷法還有Pollard-Rho等 (你的米勒沒拼錯 XD) : 3. : 這幾年有幾篇文章,提出一個deterministic的方法可以在你給定一個x時, : 回答你x是否為質數. 不過我沒去看, 只是聽老師上課提過.XD : 能回答你的都只是這些概念性的問題...不好意思了... : 如果有興趣我可以再幫你細查 ^^ 另外如果你不嫌麻煩的話 建質數表也是一個(古老的(?))方法 它的Big-O是O(表的大小) 判斷的數字則最大到表內最大質數的下一個質數的平方減一 -- 'Oh, Harry, dont't you see?' Hermione breathed. 'If she could have done one thing to make absolutely sure that every single person in this school will read your interview, it was banning it!' ---'Harry Potter and the order of the phoenix', P513 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.240.54