【Python】素数を見つける方法　プログラム付き

こんにちは、にわこまです。

今回は、pythonで素数を見つけるプログラムを作成します。とても簡単なプログラムであるため、ぜひ見ていってくだざい。

誤字脱字など何かございましたらご連絡お願いいたします。

スポンサードサーチ

素数を見つける方法

素数とは、1とその数字でしか割り切ることが出来ない正の整数（自然数）です。

例

「11」の場合、「11」の約数は「1, 11」です。よって「11」は素数です。

「15」の場合、「15」の役数は「1, 3, 5, 15」です。よって「15」は素数ではありません。

プログラム

以下に素数を見つけるプログラムを示します。

# 素数を見つけるプログラム
# =====================================
# 素数とは
# １とその数字でしか割り切れない数字のこと
# =====================================

def getPrimeNum(n):
    pn = [1]
    for i in range(2, n+1):
        flag = True
        for j in pn[1:]:
            if(i % j == 0):
                flag = False
                break
        if(flag):
            pn.append(i)
    return pn

if __name__ == '__main__':
    n = 100
    pn = getPrimeNum(n)
    print(pn)

コードの解説

7行目から17行目の「getPrimeNum」は、素数を見つける関数です。

関数getPrimeNumの引数「n」は、素数を見つける範囲を指定しています。

例えば、10である場合は1から10の間にある素数を見つけます。

8行目の「pn」は、素数を代入するリストです。初期値として「1」を代入しています。

9行目から16行目の「for文」は、範囲内の数字の数だけ繰り返し処理を行います。

10行目の「flag」は、素数であるかどうかを判定するための変数です。初期値として「True」を代入しています。

11行目から14行目の「for文」は、pnの1番目以降の数字の数だけ繰り返し処理を行います。つまり、「1」以降の素数を繰り返します。

12行目の「if文」は、数字を割り切れるかを判定しています。

「True」の場合（割り切れた場合）は、その数字は素数ではありません。

「1」以降の素数で、全て「False」の場合（割り切れない場合）は、その数字は素数となります。

13行目の「flag」には、「False」を代入しています。

14行目の「break」は、「for文」を終了するためのものです。12行目の「if文」で「True」の場合は素数ではなく、それ以降の繰り返しは必要ないため、終了しています。

15行目のの「if文」は、「flag」によって素数かそうでないかを判定しています。

16行目は、pnに素数を追加しています。

動作確認

コマンドプロンプトを開き、プログラムが保存してあるフォルダまで移動します。移動したら以下のコマンドを入力し、実行します。

python getPrimeNumber.py

以下のように出力されれば、正しく動作しています。「n」を変えれば、様々な範囲の素数を見つけることができます。

[1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

まとめ

今回は、pythonで素数を見つけるプログラムを紹介しました。とても簡単に素数を見つけることができます。

しかし高速化していないため、1億などの大きすぎる範囲の素数を見つけようとすると、処理に時間がかかります。

最後までお読みいただきありがとうございます。

スポンサードサーチ