看板java
標 題Re: [問題] 作出可判斷質數的程式
發信站資訊傳奇 (Sat Sep 30 00:13:36 2006)
轉信站ptt!ctu-reader!ctu-peer!news.nctu!news.cis.nctu!ccnews.thu!inf
【 在
[email protected] () 的大作中提到: 】
: 試試這個 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]