久々にやったAIZU ONLINE JUDGEのこの問題で困ったことが起こったので、質問させていただきます。
問題を解くコードをPython3で書いたのですが、何回やってもTime Limit Exceed
と表示されます。証拠となるソリューションはこのリンクにあります。
何が原因で、その解決方法はないのでしょうか?
わかる方、いましたら教えてください。
なお、コードは以下のとおりです。
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()
追記:
Fumu 7さんの解法を使ったのですが、それでもTime Limit Exceeded
と表示され、入力例を試しても、正しい数値にならず以下のような数値になってしまいます。
9
2
10
一体、何が原因なんでしょうか?
ちなみに、Fumu7さんの解法を使ったコードは以下のとおりです。
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()
prime_calc
関数の引数n
が文字列型ですので、math.sqrt(n)
やrange(2, n, 2)
でエラーになってしまいます。