【 在 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 的運算方式差不多
而在一些瑣碎的地方應該是更為精簡 (這部分就純粹只是個人觀點了)
--
NPDA - Non-deterministic PushDown Automata
(不確定是否推倒自動機)
DPDA - Deterministic PushDown Automata
(確定會推倒自動機)
得証: DPDA 效率比較高
※ 來源:‧資訊傳奇 inf.csie.thu.edu.tw‧[FROM: 59-126-173-31.HINET-IP.hinet.n]
討論串 (同標題文章)