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


s1063327 (yuchu)


#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)


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

99999000 100000000

 

問題出在

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

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