質問: "__main__": main() ```
回答: 原因 確かに質問者さんのプログラムは Time Limit Exceeded (TLE) となります。これはアルゴリズム部分の実行が遅いためです。特に、各入力に対して毎回試し割りして素数判定を行っていることが実行時間を嵩ませています。 原因の割り出し方 まず、Yosh さんのコメントにあるように `main` 関数内の `print(prime(line))` を `print(42)` に変えると Wrong Answer (WA) になるため、入出力が極端に遅いわけではないと分かります。TLE の原因はアルゴリズム部分にあります。 次にアルゴリズム部分を高速化するため、素数判定部分の試し割りを高速化できないか試してみましょう。ある正の整数 `n` が素数なのかどうか小さい数から順番に試し割りするようなプログラムは、次の事実を使って繰り返しの数を減らすことができます。 * 偶数の素数は 2 のみである。 * `n` が素数かどうかは、`math.sqrt(n)` までの自然数で割り切れるかどうか調べればよい。 このことを使うと、`n` が素数かどうか調べる関数 `is_prime(n)` をこのコードのように書けます。これで n が素数かどうか O(√(n)) の時間で判定できるようになりました。 今回の問題は n 以下の素数の個数を答えるものなので、素数判定を n 回実行したあと結果を足し合わせる必要があり、全体で O(n√(n)) の時間がかかります。データセットの数を Q、与えられる n の最大値を N とすると、データセット全てを処理するには O(Q × N√(N)) の時間がかかるということになります。 それなりに高速化できましたが、実はこれでもまだ TLE します。更に高速化が必要なようです。 更なる高速化 **注意: ここから下には、AOJ 0009 の回答ネタバレが含まれます。** もう少し高速化してみましょう。よく考えると、ある数が素数かどうかの判定は最初に 1 回だけ行えばよいことに気づきます。素数判定の結果をメモしておけば、それぞれのデータセットに応じて毎回素数判定する必要はありません。 要するに、こうすればよいです。まず n の最大値 N = 999999 までそれぞれ素数判定し、次に各 n に対して答えがいくつなのかを全て計算してリストに覚えておきます。あとは与えられたデータセットごとに答えをそれぞれ出力すれだけです。 このようにすると、最初に一回だけ最大値 N まで素数判定をし、あとはデータセットの個数 Q の分だけ出力をすればよいです。こうすると全体の計算量は O(N√(N) + Q) となり、高速化できます。 ここまで高速化すると、TLE にならなくなります (実際のコード)。 また、実は更に高速化できます。素数判定部分で、それぞれの n について試し割りするかわりにエラトステネスのふるいを使えばよいです。実際 AOJ 0009 の Solution の多くはこの形で実装されています。