AIZU ONLINE JUDGEの0009でWrong Answerと表示された。
AIZU ONLINE JUDGEの0009の問題に苦戦し続けている人です。
前回の質問で私がベストアンサーに選んだアルゴリズムを使って見たのですが、今度は「Wrong Answer」となります。原因を調べるべく、以下のテスト用に用意した数字を入力して出力すると、
10
3
11
100
999999
以下のようになり、
1
1
2
31
333331
本来n % i == 0
になるとFalse
になるはずのflag
がFalse
になっていないのがわかりました。
これの原因は何でしょうか?解決案も教えてください。
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()