46833


[AIZU ONLINE
JUDGE](http://judge.u-aizu.ac.jp/onlinejudge/)の0009の問題に苦戦し続けている人です。

[前回の質問](https://ja.stackoverflow.com/q/45304/13972)で私がベストアンサーに選んだアルゴリズムを使って見たのですが、今度は「[Wrong
Answer](http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3049887#2)」となります。原因を調べるべく、以下のテスト用に用意した数字を入力して出力すると、

[code]

    10
    3
    11
    100
    999999
    
[/code]

以下のようになり、

[code]

    1
    1
    2
    31
    333331
    
[/code]

本来`n % i == 0`になると`False`になるはずの`flag`が`False`になっていないのがわかりました。

これの原因は何でしょうか？解決案も教えてください。

[code]

    import math
    import sys
    
    sup = 1000000
    
    is_prime = [0] * sup
    
    count = [0] * sup
    
    def sieve():
        is_prime[2] = 1
        for n in range(3,sup,2):
            flag = True
            for i in range(3, int(math.floor(math.sqrt(n) + 1)), 2):
                if n % i == 0:
                    flag = False
                    break
                if flag:
                    is_prime[n] = 1
    
    def precount():
        for n in range(2, sup):
            count[n] = count[n-1] + is_prime[n]
    
    def main():
        sieve()
        precount()
    
        l = []
    
        for line in sys.stdin:
            l.append(int(line))
    
        for line in l:
             print(count[line])
    
    if __name__ == "__main__":
        main()
    
[/code]


CC BY-SA 4.0
2018-07-22T09:43:50.487
46832
2018-07-22T11:47:59.313
2018-07-22T11:41:54.897
13972
26886
question
python python3
AIZU ONLINE JUDGEの0009でWrong Answerと表示された。


最初に、あなたのコードはいわゆるエラトステネスの篩(Sieve of
Eratosthenes)とは全く関係ないので、関数名を`sieve`にするのはやめておいた方が良いですね。

さて、あなたのコードはこんな構造にするつもりなのですよね。

[code]

    # 2は素数だよ
    is_prime[2] = 1
    # 3以上の奇数について
    for n in range(3,sup,2):
    |   # ここで`flag`に`n`が素数かどうかの判定結果を入れる
    |   # ...
    |   # 判定が真なら
    |   if flag:
    |   |   # `n`は素数だよ
    |_  |_  is_prime[n] = 1
    
[/code]

(`|_`はインデントの範囲を明示するために入れているので、当然そのままでは動きません。)

ところが実際のあなたのコードのインデントをよくみてください。

[code]

    # 2は素数だよ
    is_prime[2] = 1
    # 3以上の奇数について
    for n in range(3,sup,2):
    |   flag = True
    |   for i in range(3, int(math.floor(math.sqrt(n) + 1)), 2):
    |   |   if n % i == 0:
    |   |   |   flag = False
    |   |   |_  break
    |   |   if flag:
    |_  |_  |_  is_prime[n] = 1
    
[/code]

`if flag:`のブロックが`for i
in`のブロックの中に入ってしまってます。つまり「`n`が素数かどうかの判定」をするためのループが終わってからでなく、ループの中で毎回`flag`を判定して真なら`is_prime[n]
=
1`を実行してしまっています。(普通は`flag`が`False`になって`break`するまでなんども`flag`が`True`のまま繰り返すはずですよね。)

また√nが小さな値の場合、`for i in`のループは一度も実行されませんので、`is_prime[n] =
1`の行も全く実行されなくなります。`n`が比較的小さな値の場合に素数と判定されていないのはそのためです。

あなたの意図通りの処理をさせたいなら、インデントはこうなるはずです。

[code]

    def sieve(): # この関数名はやめましょう…
        is_prime[2] = 1
        for n in range(3,sup,2):
            flag = True
            for i in range(3, int(math.floor(math.sqrt(n) + 1)), 2):
                if n % i == 0:
                    flag = False
                    break
            if flag:
                is_prime[n] = 1
    
[/code]

ちなみに以前のあなたのコードよりはかなり高速化されているでしょうが、厳しい時間制限があるなら、通過するかどうかは微妙な実行時間がかかりますね。


CC BY-SA 4.0
2018-07-22T11:27:28.703
46833
2018-07-22T11:47:59.313
2018-07-22T11:47:59.313
13972
13972
46832
answer


既に回答が出ていますので、蛇足ながら追加情報などを。

以下の様にすれば `flag` 変数は必要ないかと。

[code]

    def sieve():
      is_prime[2] = 1
      for n in range(3, sup, 2):
        for i in range(3, int(math.sqrt(n)) + 1, 2):
          if n % i == 0:
            break
        else:
          is_prime[n] = 1
    
[/code]


CC BY-SA 4.0
2018-07-22T11:36:58.143
46835
2018-07-22T11:36:58.143
46832
answer