※ 引述《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