作者qrtt1 (愚者)
看板java
標題Re: [問題] 作出可判斷質數的程式
時間Fri Sep 29 09:22:40 2006
※ 引述《TonyQ (骨頭)》之銘言：
: ※ 引述《[email protected] ( )》之銘言：
: : 往前找找之前的文章，這算是月經題了....
: : 不過....要會寫程式，真的要懂得去思考....不然程式永遠寫不出來。
: : 你老師還算仁慈，至少還告訴你們要開根號，我以前老師就很殘忍，第一
: : 個作業就是要我們算出第一萬個質數的值是多少，而且是要在一分鐘內，
: : (當時的機器是Pentium100，用暴力法找到一定要花十分鐘以上)，一個星
: : 期後的小考要上機考....寫不出來的話，後面就可以不用來了....但除此
: : 之外就沒任何提示了。
: 一萬個質數要怎麼找會比較有效率啊 真好奇XD
: 動態規劃法好像可以派的上用場？ (將找到的質數記錄下來再做處理...)
: 不過怎麼想好像還是有點累贅
: 我的作法是 除2以外取奇數 (因為偶數會被2整除:P)
: 待測數是從小到大開始 將已歸類為質數的記錄在list中
: 用待測數 去比對list中比待測數開根號小的質數是否能整除
: 主要的時間消耗應該是在比對質數陣列中
: 這部份不曉得有沒有更好的方法 :P (比開根號還好用的)
: 這時間複雜度好像也不是那麼好算 XD
另一個簡單的作法就是動態規劃啊:)
http://mathworld.wolfram.com/PrimeFactorization.html
看看第一張表 :P
ex. 求1~200中為質數者
N = {4, 5, 6, 7, 8, 9, ................. 200}
DP_TABLE = {2, 3} <-- 放質數
for each in N
for each in DP_TABLE
if N.e % DP.e == 0
// not prime
del N.e in N
end if
if find prime, add to DP_TABLE
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.26.34.213