#13708: TLE求解 測試通過但實驗時不會過


s1063327 (yuchu)

學校 : 元智大學
編號 : 77843
來源 : [114.32.39.18]
最後登入時間 :
2019-01-28 17:00:33
a121. 質數又來囉 | From: [60.250.52.154] | 發表日期 : 2018-04-12 14:21

#include<iostream>
using namespace std;

int main() {
int a, b;
int c=0,z=0;
while (cin >> a, cin >> b) {
for ( a=a; a <= b; a++) {
for (int i = 1; i <= a; i++) {
if (a%i == 0)
c++;
}
if (c == 2)
z++;
c = 0;
}
cout << z<<endl;
z = 0;
}
return 0;
}

 
#13728: Re:TLE求解 測試通過但實驗時不會過


snakeneedy (蛇~Snake)

學校 : 國立高雄師範大學附屬高級中學
編號 : 7661
來源 : [114.40.8.251]
最後登入時間 :
2023-01-25 19:16:06
a121. 質數又來囉 | From: [36.231.25.193] | 發表日期 : 2018-04-14 22:23

TLE 表示程式的效率有問題,可以試試看跑下面這組測資

99999000 100000000

 

問題出在

for (int i = 1; i <= a; i++) {
    if (a%i == 0)
        c++;
}

每判斷一個數 n 是不是質數,都得從 1 計到 n 才能得到結果,又重複 1000 次肯定拿 TLE;可以思考怎麼優化判斷方法:
比如數學上會只拿根號以下的數來求餘,或其他方法……

 
 
ZeroJudge Forum