【Python】素数判定法 ※随時追加

はじめに

Pythonで素数判定を行うプログラムを実装してみた。
まだアルゴリズムを学び始めたばかりの初心者のため、学習進度に伴って簡単な手法から順次アウトプットしていくことにする。

素数判定とは

定義や概要などはWikipediaを参照。

素数判定の実用的な利用法の1つとしては、RSA暗号など。

試し割り法

概要

簡単に言うと、判定する数nを小さい整数から順に割ってみて、n以外のどれでも割り切れない場合、nは素数だとなる。
最も理解しやすいアルゴリズムだが、計算量はどうしても多くなってしまう。

実装

# nは素数であるか判定する
n = int(input("素数判定を行う数を入力："))

# nが1以下の場合　→　素数ではない
if n <= 1:
    print(f"{n}は素数ではありません")

# nが2以上の場合 → 2～(n-1)の数で割ってみて、どれかで割れたらループを抜ける
else:
    for i in range(2, n):
        if n % i == 0:
            print(f"{n}は素数ではありません")
            break
        
    # (n-1)までのどの数でも割れない場合 → 素数である
    else:
        print(f"{n}は素数です")

出力結果

演算速度を確認したいので、入力する素数は大きめにしてみた。

素数判定を行う数を入力：9973
9973は素数です

9973は、4桁以下で最大の素数。
Jupyter Notebook上でテストしてみたところ、この程度の大きさの数であれば即座に結果が出力された。

感想

あくまで試し割り法をベースとする場合でも、もっと効率的なコードは多分書ける。

思いついたので言うなら、ループを回す前にあらかじめ偶数を除外するとか。
ループを回す条件も √n までで良いという話らしいが、数学の学習を多少しないと今の自分には難しそうだ。

コードの改良・その他のアルゴリズムで実装などは、追々やっていく予定。