作者tw00088437 (喵貓 loves fish)
看板C_and_CPP
標題[問題] 判斷質數的程式 覺得簡單但一直超時
時間Sun Oct 25 17:38:03 2009
http://zerojudge.tw/ShowProblem?problemid=d447
題目
使用平台:dev c++
就只是要判斷質數 只是我第一次送出TLE(超過一秒)
後來我建了一些表又用了6N+-1判斷法
還是TLE = =
請問還有哪些地方可以改進變得更快@@
#include<iostream>
#include<cmath>
using namespace std;
int N,a,b,c;//c =counter
int main()
{
while(cin>>N)
{
b=1;
c=0;
a=43;
if(N%2==0&&N!=2)
cout<<"no"<<endl;
else if(N%3==0&&N!=3)
cout<<"no"<<endl;
else if(N%5==0&&N!=5)
cout<<"no"<<endl;
else if(N%7==0&&N!=7)
cout<<"no"<<endl;
else if(N%11==0&&N!=11)
cout<<"no"<<endl;
else if(N%13==0&&N!=13)
cout<<"no"<<endl;
else if(N%17==0&&N!=17)
cout<<"no"<<endl;
else if(N%19==0&&N!=19)
cout<<"no"<<endl;
else if(N%23==0&&N!=23)
cout<<"no"<<endl;
else if(N%29==0&&N!=29)
cout<<"no"<<endl;
else if(N%31==0&&N!=31)
cout<<"no"<<endl;
else if(N%37==0&&N!=37)
cout<<"no"<<endl;
else if(N%41==0&&N!=41)
cout<<"no"<<endl;
else if(N%43==0&&N!=43)
cout<<"no"<<endl;
else
{
while(a<=sqrt(N))
{
if(N%a==0)
{ cout<<"no"<<endl;
b=0; }
a=a+(c%2)*2+2;
c++;
}
if(b)
cout<<"yes"<<endl;
}
}
return 0;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.103.110
推 carlcarl:是在程式執行時建表 不是在code中輸入幾個case這樣吧 10/25 17:52
→ carlcarl:而且你給的case也太少= =a 10/25 17:52
→ VictorTom:N輸入後就不變, 所以你不需要每次迴圈都sqrt(N), 算過一 10/25 19:01
→ VictorTom:次存下來就好, sqrt()的速度之慢應該不是/或%可以比的. 10/25 19:01
→ VictorTom:最好也能分析輸入範圍, 決定是否連那一次sqrt都不要算, 10/25 19:02
→ VictorTom:改用a*a來取代. 話說, 每個數都%那幾個數判斷在先真的會 10/25 19:03
→ VictorTom:比較快嗎@_@" 10/25 19:03
→ tw00088437:我剛初學沒多久 不知道怎樣比較有效率啊 哭哭>< 10/25 19:18
→ tw00088437:而且在上傳之前有辦法先在自己評台測出效率嗎@@ 10/25 19:27
→ tw00088437:我跑的時候打到很大的數字也都是馬上就輸出結果了不到 10/25 19:28
→ tw00088437:一秒@@" 10/25 19:28
→ MOONRAKER:顯然他的時間限制比你想像的嚴格。 10/25 22:26
→ ledia:至少要幾十萬組大數字來測吧 10/25 22:26
→ ledia:你可以試試從 2 測到 2147483647 的總計時間 10/25 22:28
推 carlcarl:程式打多就會有感覺了0.0a 10/25 23:44
→ tw00088437:哪位高手可以寫個不ＴＬＥ的程式給小弟看ＱＱ 10/26 01:04
→ tw00088437:順便解釋一下為何效率比較好＠＠？ 10/26 01:05
→ MOONRAKER:他都叫你建表了 想想看怎麼建 0 - k 的表吧 10/26 01:41
→ MOONRAKER:然後考慮 對 [ 0, 2147483647 ] 而言，k 要為多少 10/26 01:41
→ MOONRAKER:幹嘛寫給你看，不是你自己寫出來的有什麼意思啊 10/26 01:42
推 carlcarl:先在程式一開始把所有範圍內的質數抓出來 input就直接對 10/26 01:59