Re: [問題] 作出可判斷質數的程式
※ 引述《tkcn.bbs@inf.csie.thu.edu.tw (小安)》之銘言：
: 【 在 Saren.bbs@bbs.wretch.cc () 的大作中提到: 】
: : 試試這個 i從2開始 一直到根號n
: : for(i=2;i<=sqrt(n);i++) {
: : if(n%i) {
: : system.out.println(n+"is prime number!");
: : i=n;
: : }
: : }
: : 那它的時間複雜度降到n^(1/2)
: 對一個數檢查是否為質數是只需 n^(1/2) 沒錯
: 但是這裡應該用檢查 n 個數來比較才是，所以應該是 n^(3/2)
: 而你所提的演算法其實是可以改進的，
: 只要把目前的 for 迴圈的 i 改成只跑已經算出來的質數 (當然，同樣是小於 sqrt(n) )
: 也就是前面 TonyQ 所提過的方法
: 我所提的方法其實也是這樣，雖然看起來是 O(n^2)
: 但其實與 TonyQ 的運算方式差不多
: 而在一些瑣碎的地方應該是更為精簡 (這部分就純粹只是個人觀點了)
看看這個連結吧: http://primes.utm.edu/prove/prove4_3.html
對一個數檢查是否為質數並不需要到 O(n^(1/2)) 喔
這個連結指出 O((log n)^12 f(log log n)) where f is a polynomial.
所以求質數的方法還可以再改進的
至少目前為止 po 出來的程式碼都沒有我所記錄過的 code 還快 @_@
--
是不是該移駕到 prob_solve 板討論了呢 XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.205.85
推
09/30 10:09, , 1F
09/30 10:09, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 9 之 9 篇)：