AIZU ONLINE JUDGEの0009で何回やってもTime Limit Exceedと表示されます。


久々にやったAIZU ONLINE
JUDGEの[この問題](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009&lang=jp)で困ったことが起こったので、質問させていただきます。

問題を解くコードをPython3で書いたのですが、何回やっても`Time Limit
Exceed`と表示されます。証拠となる[ソリューションはこのリンクにあります。](http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2996321#2)

何が原因で、その解決方法はないのでしょうか？  
わかる方、いましたら教えてください。

なお、コードは以下のとおりです。

[code]

    import sys
    
    def prime_calc(n):
        if n < 2:
            return False
        else:
            i = 2
            while n > i:
                if n % i == 0:
                    return False
                else:
                    i += 1
        return True
    
    def prime(n):
        cnt = 0
        for i in range(0, n+1):
            ans = prime_calc(i)
            if ans is True:
                cnt = cnt + 1
        return cnt
    
    def main():
        l = []
    
        for line in sys.stdin:
            l.append(int(line))
    
        for line in l:
            print(prime(line))
    
    if __name__ == "__main__":
        main()
    
[/code]

追記:  
Fumu 7さんの解法を使ったのですが、それでも`Time Limit
Exceeded`と表示され、入力例を試しても、正しい数値にならず以下のような数値になってしまいます。

[code]

    9
    2
    10
    
[/code]

一体、何が原因なんでしょうか？

ちなみに、Fumu7さんの解法を使ったコードは以下のとおりです。

[code]

    import math
    import sys
    
    def prime_calc(n):
        if n < 2:
            return False
        elif n==2 or n==3 or n==5 or n==7:
            return True
        else:
            rootN = math.floor(math.sqrt(n))
            i = 11
            while rootN > i:
                if n % i == 0:
                    return False
                else:
                    i += 2
    
        return True
    
    def prime(n):
        cnt = 0
        for i in range(2, n+1):
            ans = prime_calc(i)
            if ans is True:
                cnt = cnt + 1
    
        return cnt
    
    def main():
        l = []
    
        for line in sys.stdin:
            l.append(int(line))
    
        for line in l:
            print(prime(line))
    
    if __name__ == "__main__":
        main()
    
[/code]




## 原因

確かに質問者さんのプログラムは Time Limit Exceeded (TLE)
となります。これはアルゴリズム部分の実行が遅いためです。特に、各入力に対して毎回試し割りして素数判定を行っていることが実行時間を嵩ませています。

## 原因の割り出し方

まず、[Yosh さんのコメント](https://ja.stackoverflow.com/questions/45304/aizu-online-
judge%E3%81%AE0009%E3%81%A7%E4%BD%95%E5%9B%9E%E3%82%84%E3%81%A3%E3%81%A6%E3%82%82time-
limit-
exceed%E3%81%A8%E8%A1%A8%E7%A4%BA%E3%81%95%E3%82%8C%E3%81%BE%E3%81%99#comment47301_45304)にあるように
`main` 関数内の `print(prime(line))` を `print(42)` に変えると Wrong Answer (WA)
になるため、入出力が極端に遅いわけではないと分かります。TLE の原因はアルゴリズム部分にあります。

次にアルゴリズム部分を高速化するため、素数判定部分の試し割りを高速化できないか試してみましょう。ある正の整数 `n`
が素数なのかどうか小さい数から順番に試し割りするようなプログラムは、次の事実を使って繰り返しの数を減らすことができます。

  * 偶数の素数は 2 のみである。
  * `n` が素数かどうかは、`math.sqrt(n)` までの自然数で割り切れるかどうか調べればよい。

このことを使うと、`n` が素数かどうか調べる関数 `is_prime(n)`
を[このコード](https://wandbox.org/permlink/T44J5dWQtcbJty4h)のように書けます。これで 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 にならなくなります
([実際のコード](https://wandbox.org/permlink/80givVKiFIsOE6hy))。

また、実は更に高速化できます。素数判定部分で、それぞれの n について試し割りするかわりにエラトステネスのふるいを使えばよいです。実際 [AOJ 0009
の Solution](http://judge.u-aizu.ac.jp/onlinejudge/solution.jsp?pid=0009)
の多くはこの形で実装されています。




## 原因

確かに質問者さんのプログラムは Time Limit Exceeded (TLE)
となります。これはアルゴリズム部分の実行が遅いためです。特に、各入力に対して毎回試し割りして素数判定を行っていることが実行時間を嵩ませています。

## 原因の割り出し方

まず、[Yosh さんのコメント](https://ja.stackoverflow.com/questions/45304/aizu-online-
judge%E3%81%AE0009%E3%81%A7%E4%BD%95%E5%9B%9E%E3%82%84%E3%81%A3%E3%81%A6%E3%82%82time-
limit-
exceed%E3%81%A8%E8%A1%A8%E7%A4%BA%E3%81%95%E3%82%8C%E3%81%BE%E3%81%99#comment47301_45304)にあるように
`main` 関数内の `print(prime(line))` を `print(42)` に変えると Wrong Answer (WA)
になるため、入出力が極端に遅いわけではないと分かります。TLE の原因はアルゴリズム部分にあります。

次にアルゴリズム部分を高速化するため、素数判定部分の試し割りを高速化できないか試してみましょう。ある正の整数 `n`
が素数なのかどうか小さい数から順番に試し割りするようなプログラムは、次の事実を使って繰り返しの数を減らすことができます。

  * 偶数の素数は 2 のみである。
  * `n` が素数かどうかは、`math.sqrt(n)` までの自然数で割り切れるかどうか調べればよい。

このことを使うと、`n` が素数かどうか調べる関数 `is_prime(n)`
を[このコード](https://wandbox.org/permlink/T44J5dWQtcbJty4h)のように書けます。これで 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 にならなくなります
([実際のコード](https://wandbox.org/permlink/80givVKiFIsOE6hy))。

また、実は更に高速化できます。素数判定部分で、それぞれの n について試し割りするかわりにエラトステネスのふるいを使えばよいです。実際 [AOJ 0009
の Solution](http://judge.u-aizu.ac.jp/onlinejudge/solution.jsp?pid=0009)
の多くはこの形で実装されています。

