45445


久々にやった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]


CC BY-SA 4.0
2018-07-04T07:43:24.153
45304
2018-07-17T10:17:26.860
2018-07-17T10:17:26.860
26886
26886
question
python python3 アルゴリズム
AIZU ONLINE JUDGEの0009で何回やってもTime Limit Exceedと表示されます。


私はAIZU ONLINE JUDGEを試したことがありませんが、`for line in
sys.stdin:`は他の回答例でも使われていますので、コードは動作しておりCPU時間9:99でタイムアップ(目標1秒以内)となっている前提で記述します。

渡される複数のデータセットを配列`l`に登録し、個々の要素について個別に0からその数値までエラトステネスの篩を掛けているのがCPU時間を消費する要因として目につきます。

例えばデータセットが`[3, 5]`と入力された場合に、提示されたコードでは

  1. 最初の要素で3までの素数をカウントするため、0～3まで4回ループを回してそれぞれの値をprime関数に渡して素数計算をする  
prime関数は下記の動作を行う

    1. prime_calc(0)を呼び出してFalseを返す
    2. prime_calc(1)を呼び出してFalseを返す
    3. prime_calc(2)を呼び出す  
prime_calc関数は下記の動作を行う

      1. 2は素数なのでTrueを返す
    4. prime_calc(3)を呼び出す  
prime_calc関数は下記の動作を行う

      1. 2は素数なのでTrueを返す
      2. 3が素数か判定するため、1回ループを回してTrueを返す
  2. 5までの素数をカウントするため、0～5までループを回して上記の処理を行う

データセットの個数は30個まで、値は(1 ≤ n ≤ 999,999) ですので、個数や値が大きいと計算回数が非常に多くなります。

下記の観点から計算回数を減らすよう、コードを見直してみてください。

  1. ループの回数を押さえる  
例えば配列`l`に登録される数値が[5, 10,
10]の場合には、まず最小値である5以下の素数が[2,3,5]の3個であることを計算して、個数を変数に保存しておきます。  
次に6～10の素数が[7]の1個であることを計算します。上記の変数と個数を合計して10以下の素数の個数を求めて変数に保存します。  
最後に3つ目の要素10以下の素数は既に計算済みですので、計算をせずに4を返します。

  2. 無駄なループをしない  
`0,1`は素数ではないので、`range(0, n+1):`を`range(2, n+1):`のように書き換えてループの回数を減らします。

  3. ループの回数を減らす  
`4,6,8...`といった2の倍数に対して素数判定をスキップすると、ループの回数が1/2に減ります。

素数計算の高速化にはこれ以外にも手法がありますが、まずは速度が遅くなる原因の計算回数を省略するためにロジックを見直すことで解決方法を検討してはいかがでしょうか。


CC BY-SA 4.0
2018-07-04T09:46:15.693
45307
2018-07-04T09:46:15.693
9820
45304
answer


素数の性質を使っていないので、無駄が多いと思います。

１）nの約数は、√n (ルート n)を超えることはない(1,000,000の最大の約数は、高々1,000)  
という性質を使えば、

[code]

    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
    
[/code]

を以下のように修正できて、whileループの回数を n から (√n)/2 に抑えられます。  
nが最大の999,999だった場合は、ループ回数(ほぼ実行時間に比例する)が2000分の1まで減ります。どんなinputが与えられるかに依存しますが、実行時間を2桁程度減らせるのではないかと思いますから、1秒以内に収まる可能性が高くなります。

[code]

    import math
    def prime_calc(n):
        if n < 2 :
            return False            
        elif n==2 or n==3 or n==5 or n==7: #設問にあるヒント、"例えば 10 以下の素数は、2, 3, 5, 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
    
[/code]


CC BY-SA 4.0
2018-07-04T12:28:26.820
45312
2018-07-04T12:28:26.820
217
45304
answer


採用しているアルゴリズムに問題があると思います。なので素数判定のアルゴリズムについて検索することをおすすめします。

N以下の素数をすべて列挙するアルゴリズムでO(N)に近い時間計算量を持つものが知られています。ただし、この問題に関してはデータセットが30まであるので、もうひと工夫必要だと思われます。

**注意：以下ネタバレになります**  
エラトステネスのふるいというアルゴリズムを使えば、N以下の素数をO(N*log(log(N)))の時間で列挙することができます。これは簡単に言えば、数を小さい方から見ていって、その数の倍数に「素数でない」印をつけていくというものです。

コードは次のようなものが考えられます。  
(以下のコードは本番で試したわけではないので、何か問題があればレスポンスをください）

[code]

    import sys
    
    N = 10**6
    
    is_prime = [True for _ in range(N)]
    
    c = 0
    count = [0 for _ in range(N)]
    
    # sieve
    p = 0
    is_prime[0] = is_prime[1] = False
    
    for i in range(2,N):
        if is_prime[i]:
            c += 1
            for j in range(i*i, N, i):
                is_prime[j] = False
        count[i] = c
    
    for line in sys.stdin:
        print(count[int(line)])
    
[/code]


CC BY-SA 4.0
2018-07-09T04:08:28.627
45440
2018-07-09T09:08:08.253
2018-07-09T09:08:08.253
13199
13199
45304
answer


## 原因

確かに質問者さんのプログラムは 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)
の多くはこの形で実装されています。


CC BY-SA 4.0
2018-07-09T08:02:44.367
45445
2018-07-09T08:08:09.547
2018-07-09T08:08:09.547
19110
19110
45304
answer


皆さんが回答されているように、エラトステネスのふるい、をつかうのが適切なようです。  
下記のコード(データセットの読み込みと、回答の出力の手前まで）で、実行時間は 0.355273962020874 秒でした。python 3.6.4、
PCは（Window10, CPU:core i7-3770 3.4GHz, Ram:8GB)を使用。

エラトステネスのふるいのための初期設定で、0,1,0,1,0,0
のパターンを追加していく（４+6nから始まる６つの数字は、「偶数、不明、偶数、不明、偶数、３の倍数」となることを利用）のが許されるかどうか微妙かもしれませんが、ループ回数が減って実行速度短縮に効果がありました。

[code]

    import sys
    import math
    import time
    
    start=time.time()
    
    primes=[0,0,1,1] # 0,1は素数ではない、2,3は素数
    for i in range (166666):
        primes += [0,1,0,1,0,0] # 4以降は、2の倍数、不明、2の倍数、不明、２の倍数、3の倍数、のパターンを繰り返す
    print(len(primes))
    
    #エラストテネスの篩(ふるい)　2と3の倍数は処理済みなので、5以降の素数でふるい
    for j in range(5,1000,1):
        if primes[j]==1: #素数なら
            for k in range(2,math.floor((1000-j)/j),1):
                primes[j*k]=0 #その倍数を素数から外す
    
    primesCount = [0,0,1,2] #
    primesCountAcc = 2
    for j in range(4,1000000,1):
      primesCountAcc += primes[j]
      primesCount += [primesCountAcc]
    
    print("Elapsed time:",time.time()-start," seconds") #所要時間
    #データ確認
    print("数: 素数なら１　-　数以下素数の数")
    for j in range(30): 
        print (j," : ",primes[j],"-",primesCount[j])
    
[/code]


CC BY-SA 4.0
2018-07-11T22:18:05.213
45526
2018-07-11T22:18:05.213
217
45304
answer