このソースコードについて

質問

AOJにてこのコードを提出したところTime Limit Exceededでドロップされました。
Visual studio 2013 で動かしたところ特に怪しい挙動や間違いを出力することはなかったのですが。。。
ちなみに言語はC++です。
問題のURL　http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0056

#include<iostream>
#include<math.h>
using namespace std;
int p[20000],d;

void primefinder(int a){
p[0] = 2;
int k, l = 0;
for (int i = 3; i <= a; i++){
k = (int)sqrt(i);
for (int j = 2; j <= k + 1; j++){
if (j == k + 1){ p[++l] = i;}
else if (i%j == 0)break;
}
}
d = l + 1;
}

int main(){
int n,m,q,count;
while ((cin >> n), n){
count = 0;
m = n / 2;
primefinder(m);
for (int i = 0; i < d; i++){
q = n - p[i]; if (q <= 1)continue;
for (int j = 2; j <= (int)sqrt(q)+1; j++){
if (j == (int)sqrt(q) + 1)count++;
else if (q%j == 0)break;
}
}
cout << count << endl;

}
}

回答No.2

maiko0333

ロジックの改善をしましょう。
例えば、
for (int j = 2; j <= k + 1; j++){
　if (j == k + 1){ p[++l] = i;}
　else if (i%j == 0)break;
　}
}
ここに無駄があります。
２重ループですとかなりロスしているのでは？
k=9の時、jは2から増えていき、k+1まで3,4,5,6,7,8,9,10までループし、
if (j == k + 1){ p[++l] = i;}というのは最後のk=10の時だけですよね。
では、外に出しましょう。
例えば、
for (int j = 2; j <= k + 1; j++){
if (i%j == 0)break;
}
if(j==k) p[++l] = i;
のほうが速いはずですね。

回答No.1

f272

原因ははっきりしていて「Time Limit Exceeded」ですね。ようするに時間がかかりすぎているということです。