0

AIZU ONLINE JUDGEの0009の問題を解くために以下のようなコードを提出したのですが、「Runtime Error」が出てしまいます。簡単な問題かもしれませんが原因がわかる方、お答えください。

import math
import sys

def prime_calc(n):
    rootN = math.floor(math.sqrt(n))
    prime = [2]
    data = [i + 1 for i in range(2,n,2)]
    while True:
        p = data[0]
        if rootN <= p:
            return len(prime + data)
        prime.append(p)
        data = [e for e in data if e % p != 0]

def main():
    l = []

    for line in sys.stdin:
        l.append(int(line))        

    for line in l:
        print(prime_calc(line))

if __name__ == "__main__":
    main()

追記:tanalab2 さんの解答のとおりにしたのですが、なぜか「Runtime Error」が出てしまいます。原因は何でしょうか?

追記:tanalab2さんのご指摘の通りのコードにしました。

追記:以下の入力を試しましたが問題はありませんでした。

10
3
11
6
  • すみません。お役に立てませんでしたか。修正されたコードをご自分の環境で実行した時にどのようなエラーとTracebackが表示されるでしょうか?
    – user28902
    Commented 2018年7月17日 10:48
  • @tanalab2 なんのエラーも出てませんね。
    – Nagkei10
    Commented 2018年7月17日 10:54
  • 3
    問題文には Each dataset has an integer n (1 ≤ n ≤ 999,999) in a line. と書かれているのですが、例えば 2 が渡されたとすると、data = [i + 1 for i in range(2,n,2)] では data 変数に空の配列がセットされる事になります。そして、その後の p = data[0] で index error が発生する事になります。
    – user39889
    Commented 2018年7月17日 11:33
  • @metropolis さん 本当ですね。ロジックの問題のようですね。私のコメントは誤ってますね。誤情報のため削除しておきます。
    – user28902
    Commented 2018年7月17日 11:36
  • 2
    keito940さんの試した入力も載せたほうがよい思います。また一般論として色々な入力を試すべきです(少なくともこのコードは少なくともtanalab2さん、metropolisさんの指摘する問題を抱えているわけですし)。特にエラーで弾かれたなら、そのようなエラーを引き起こすような入力を探してみることをおすすめします。
    – letrec
    Commented 2018年7月17日 12:38

2 件の回答 2

1

問題を提出する前に、ご自分の開発環境で動作確認を行う必要があります。

ご質問のコードを動作確認のため実行したところ、
以下のエラーが発生しました。

Traceback (most recent call last):
  File "hoge4.py", line 25, in <module>
    main()
  File "hoge4.py", line 22, in main
    print(prime_calc(line))
  File "hoge4.py", line 5, in prime_calc
    rootN = math.floor(math.sqrt(n))
TypeError: must be real number, not str

標準入力から読み取った文字列を数値に変換していないことが原因と思います。

for line in sys.stdin:
        l.append(int(line))  # 文字列を整数に変換  
1

自分で皆様が指摘した部分のソースコードを確認をしたところ、
1以下のときには素数がないので0を返し、
ちょうど2のときは素数は一つだけなので1を返すようにしました。
ご回答ありがとうございました。

import math
import sys

def prime_calc(n):
    if n <= 1:
        return 0
    elif n == 2:
        return 1
    else:
        rootN = math.floor(math.sqrt(n))
        prime = [2]
        data = [i + 1 for i in range(2,n,2)]
        while True:
            p = data[0]
            if rootN < p:
                return len(prime + data)
            prime.append(p)
            data = [e for e in data if e % p != 0]

def main():
    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
        print(prime_calc(line))

if __name__ == "__main__":
    main()

追記:でも、今使ったアルゴリズムはAIZU ONLINE JUDGE的にはTime Limit Exceedなので、別な(高速)のアルゴリズムを使うといいです。でも、アルゴリズムを提供してくれたFantm21さんありがとうございました。

元記事:Pythonで作るエラトステネスのふるい

0

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。