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