※ 引述《[email protected] (愚者)》之銘言： > ※ 引述《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 》──┘ ◥ ╲ 免程式技術、硬體成本的選擇!! --