Re: [問題] 作出可判斷質數的程式
※ 引述《tachibana1@kkcity.com.tw ( )》之銘言：
: ※ 引述《sk2g.bbs@ptt.cc (ㄟ死ㄎㄟ吐狙)》之銘言：
: 往前找找之前的文章，這算是月經題了....
: 不過....要會寫程式，真的要懂得去思考....不然程式永遠寫不出來。
: 你老師還算仁慈，至少還告訴你們要開根號，我以前老師就很殘忍，第一
: 個作業就是要我們算出第一萬個質數的值是多少，而且是要在一分鐘內，
: (當時的機器是Pentium100，用暴力法找到一定要花十分鐘以上)，一個星
: 期後的小考要上機考....寫不出來的話，後面就可以不用來了....但除此
: 之外就沒任何提示了。
一萬個質數要怎麼找會比較有效率啊 真好奇XD
動態規劃法好像可以派的上用場？ (將找到的質數記錄下來再做處理...)
不過怎麼想好像還是有點累贅
我的作法是 除2以外取奇數 (因為偶數會被2整除:P)
待測數是從小到大開始 將已歸類為質數的記錄在list中
用待測數 去比對list中比待測數開根號小的質數是否能整除
主要的時間消耗應該是在比對質數陣列中
這部份不曉得有沒有更好的方法 :P (比開根號還好用的)
這時間複雜度好像也不是那麼好算 XD
--
String temp="relax"; | Life just like programing
while(buringlife) String.forgot(temp); | to be right or wrong
while(sleeping) brain.setMemoryOut(); | need not to say
stack.push(life.running); | the complier will
stack.push(scouting.buck()); | answer your life
stack.push(bowling.pratice()); | Bone everything
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.134.27.68
※ 編輯: TonyQ 來自: 220.134.27.68 (09/29 03:55)
討論串 (同標題文章)