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

Question

前提・実現したいこと

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/ツールのバージョンなど）

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

Comments

[tetsunosuke]

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

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

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

[C0dalice]

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

Answer 1

無事完成いたしました!
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)

Comments

[katoy]

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

[C0dalice]

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

[katoy]

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

[LouiS0616]

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

Answer 2

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

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

Answer 3

    while result:
        prime_list.append(n)

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

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

Comments

[C0dalice]

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

Answer 4

MemoryError

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

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

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

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

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

Comments

[C0dalice]

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