作者TonyQ (骨头)
看板java
标题Re: [问题] 作出可判断质数的程式
时间Fri Sep 29 12:36:45 2006
※ 引述《[email protected] ( )》之铭言：
: ※ 引述《[email protected] (愚者)》之铭言：
: 不过後来等到上机考过了之後，大家开始拼速度....
: 其实只要用开根号去比对，速度就快了十倍，所以只要用这方法在P100的机器上
: 跑就一定跑得进一分钟内。
: 再来就衍生出第二种方法，就是qrtt1大大讲的「动态规划」，当时我们也不知道
: 这叫动态规划，只是觉得这也是可行的方法，毕竟光是2跟3就可以去掉5/6的数量
: 了，不过，因为我们的题目是「找出第十万个质数」而非从「十万个质数找出所有
: 质数」，等到数字很大时，其实速度会被Delay(记得哟！时空背景是P100哟！)
: 後来，最後的大绝招是啥？两个放在一起用，就是开根号後用质数表去除....
: 这是我们最後想出来最快速的方法....之後就为第二个恐怖的上机考烦恼去了....
: 等到毕业後，听说，是听说哟！还有比这种方法更快速的方法....不过对当时我们
: 那群大一新生而言，最後大绝招已经快到一个境界了(最後程式码不是我测的，)，
: 只消几秒钟答案就跑出来了....再快还能多快？
动态规划(Dynamic Programming)的简介 , 一个用空间换取时间的演算法.
http://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
XD 吾所见与汝戚戚焉
我觉得还能加快的地方，应该是num的值域啦。比方说我们知道2是值数，
就在一开始的时候就不把偶数列进去一样，不过不是很容易...XD
底下是我的code
list 质数存放的空间
num 待测数
i 第几个质数
check 是否为质数
LinkedList<Integer> list=new LinkedList<Integer>();
boolean check;
for(int i=0,num=2;i<10000;){
check=true;
for(int j=0;j<list.size()&&
Math.sqrt(num)>=list.get(j);j++){
if(num%list.get(j)==0){
check=false;
}
}
if(check){
list.add(num);
System.out.print(list.get(i)+" ");
i++;
}
if(num%2==0){
num++;
}else{
num+=2;
}
}
--
String temp="relax"; | Life just like programing
while(buringlife) String.forgot(temp); | to be right or wrong
while(sleeping) brain.setMemoryOut(); | need not to say
stack.push(life.running); | the complier will
stack.push(scouting.buck()); | answer your life
stack.push(bowling.pratice()); | Bone
everything
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.134.27.68
※ 编辑: TonyQ 来自: 220.134.27.68 (09/29 12:47)