質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.62%

Python メモリーエラー 素数判定

解決済

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 432

C0dalice

score 11

前提・実現したいこと

pythonで素数判定のプログラム作成中にどう対処すればよいかわからないエラーに遭遇しました

発生している問題・エラーメッセージ

Traceback (most recent call last):
  File "D:/programming_file/python/1-2/q1-1.py", line 17, in <module>
    f(10)
  File "D:/programming_file/python/1-2/q1-1.py", line 13, in f
    prime_list.append(n)
MemoryError

該当のソースコード

def f(n):

    """
    素数判定関数です
    :param n: n以下の素数のリストを表示します
    :return:素数のリストを表示します
    """

    prime_list = []  # 素数をいれる空のリストを作成します
    result = False  # resultにFalseを代入します
    if n == 0 or n == 1:  # nが0または1の場合をあらかじめ処理しておきます
        print(prime_list)
    else:  # nが0または1でない場合
        for divide_num in range(2, n):  # 2~n-1までの数字をループします
            if n % divide_num == 0:  # nをdivide_numで割ったあまりが0の時はpassします
                pass
            else:  # 余りが0にならないときresultをTrueに変えます
                result = True
    while result:  # resultがTrueの時nをprime_listに追加
        prime_list.append(n)
    print(prime_list)  # prime_listの表示


f(10)


f(10)

試したこと

補足情報(FW/ツールのバージョンなど)

自作コードなのでそもそも素数判定できていない可能性があります。
そのような場合はどこが間違っているか教えていただければ幸いです。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • tetsunosuke

    2019/05/27 17:25

    while result: # resultがTrueの時nをprime_listに追加
    prime_list.append(n)

    このループにずっとハマってしまっているように見えます。結果、prime_listにnがずっと追加され、メモリがなくなります。

    もうちょい考えてみましょう!

    キャンセル

  • C0dalice

    2019/05/27 17:48

    ループ処理の使い方間違えてましたね... 。
    もう少し考えてみます...!

    キャンセル

回答 4

checkベストアンサー

0

    while result:
        prime_list.append(n)


の部分で、無限ループでリストに追加していくので、メモリを使い果たしてエラーになります。
ロジックをきちんと考え直しましょう。

1.素数候補として2からnまでの繰り返し
2.素数候補がそれ未満の数で割り切れるか調べる繰り返し
の二重のループになるはずです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/27 17:46

    確かに2重ループにしないとだめですねありがとうございます。

    キャンセル

0

MemoryError

リストに延々と要素を加え続けていっているからメモリが不足しているのです。
while result: ではなく if result: では。

自作コードなのでそもそも素数判定できていない可能性があります。

関数を適切に分けた方が良いです。

  • 素数判定をする関数
  • 上記の関数を利用して、一定の値以下の素数リストを作る関数

まず前者を作り、その挙動が望ましいか充分確かめてください。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/28 22:06

    ループし続けてましたね...よく考えてから質問すべきでした。すみません。
    そうですね。関数とリストを作る処理は別で行ったほうが、読みやすいプログラムになりそうです。次の素数プログラムにはその要素取り入れたいと思います。回答ありがとうございました。

    キャンセル

0

debugger をつかったり、 print() で変数の値を表示させりようにして動作状況を確かめたりするとよいです。

今回の場合なら、 
prime_list.append(n)
の前に print(prime_list) とか print(n) とかを挿入して走らせてみると何が起こっているか判明したはずです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

無事完成いたしました!
def f(n):
"""
:param n: 2より大きい自然数
"""
prime_list = []
for i in range(2, n+1):
result = True
for j in range(2, i):
if i % j == 0:
result = False
break
if result:
prime_list.append(i)
print(prime_list)

f(10)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/28 07:04

    フラグ result を使わない豊富を考えてみると良いと思います。
    他にもいろいろ工夫の余地はあります。
    (割り算実行の回数をなるべく減らす。 2 より大きい偶数での割り算はしないようにするとか ...)

    キャンセル

  • 2019/05/28 22:03

    偶数で割らない例もやってみました。それ以上工夫できなかったので素数のプログラムについて調べてみたのですが、ある数の平方根より小さい数で割れなかったら素数になるそうですね。それを実装すればかなり最適なアルゴリズムになりそうなので、取り組んでみます。
    回答ありがとうございました。

    キャンセル

  • 2019/05/29 01:44

    prime_list にそれまでに見つけた素数があるのですから、それでの割り算をするようにすると、さらに計算量が減ります。

    キャンセル

  • 2019/05/29 07:20

    素数のリストを作るのでしたら、エラトステネスの篩も試してみると良いでしょう。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.62%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る