※ 引述《[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 》──┘ ◥ ╲ 免程式技术、硬体成本的选择!! --