作者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