Re: [問題] 作出可判斷質數的程式
※ 引述《qrtt1.bbs@ptt.cc (愚者)》之銘言：
> ※ 引述《TonyQ (骨頭)》之銘言：
> : 一萬個質數要怎麼找會比較有效率啊 真好奇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
不過後來等到上機考過了之後，大家開始拼速度....
其實只要用開根號去比對，速度就快了十倍，所以只要用這方法在P100的機器上
跑就一定跑得進一分鐘內。
再來就衍生出第二種方法，就是qrtt1大大講的「動態規劃」，當時我們也不知道
這叫動態規劃，只是覺得這也是可行的方法，畢竟光是2跟3就可以去掉5/6的數量
了，不過，因為我們的題目是「找出第十萬個質數」而非從「十萬個質數找出所有
質數」，等到數字很大時，其實速度會被Delay(記得喲！時空背景是P100喲！)
後來，最後的大絕招是啥？兩個放在一起用，就是開根號後用質數表去除....
這是我們最後想出來最快速的方法....之後就為第二個恐怖的上機考煩惱去了....
等到畢業後，聽說，是聽說喲！還有比這種方法更快速的方法....不過對當時我們
那群大一新生而言，最後大絕招已經快到一個境界了(最後程式碼不是我測的，)，
只消幾秒鐘答案就跑出來了....再快還能多快？
--
┌─────◆ＫＫＣＩＴＹ◆─────┐ ◢ ╱ 想要成立班系社團站台嗎?
│ bbs.kkcity.com.tw │ █▉ ─ KKcity即日起開放BBS站申請囉!
└──《From:61.62.107.41 》──┘ ◥ ╲ 免程式技術、硬體成本的選擇!!
--
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 4 之 9 篇)：