こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

-広告-

締切り済みの質問

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

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;

}
}

投稿日時 - 2015-10-10 17:15:28

QNo.9061708

困ってます

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

-広告-
-広告-

回答(2)

ANo.2

ロジックの改善をしましょう。
例えば、
for (int j = 2; j <= k + 1; j++){
 if (j == k + 1){ p[++l] = i;}
 else if (i%j == 0)break;
 }
}
ここに無駄があります。
2重ループですとかなりロスしているのでは?
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;
のほうが速いはずですね。

投稿日時 - 2015-10-10 20:46:36

-広告-

ANo.1

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

投稿日時 - 2015-10-10 17:48:41

-広告-
-広告-

あなたにオススメの質問

-広告-
-広告-