素数判定アルゴリズム

#はじめに
今回は素数かどうかを判定するアルゴリズムをpythonを用いて行おうと思います。
素数の定義ですが、簡単に言えば以下のようになります。
「素数とは、1とその数自身以外に正の約数を持たない、1より大きい整数」
この定義を元にして、いくつかの素数判定アルゴリズムを実装してみたいと思います。
素数(Wikipedia)

P1：一番シンプルな実装方法

素数の定義から単純に考えると、1とその数自身以外で割り切れないことを確認すれば、素数かどうかを判定できます。つまり、1 から n まで順々に素数かどうか判定すればよいというわけです。

• n を判定したい数とする
• 2 から n - 1 までで n を割ってみる
  • もしどこかで割り切れたら n は合成数
• 最後まで割り切れなかったら n は素数

# 一番シンプルな方法
def judge_prime_num_p1(int_num):
    for i in range(2, int_num):
        if int_num % i == 0:
            print("{0} is composite".format(int_num))
            return

    print("{0} is Prime".format(int_num))

if __name__ == "__main__":
    judge_prime_num_p1(31)

Terminalでの実行結果

# 実行結果
31 is Prime

##P2：処理回数を減らす実装方法
P1では愚直に1からnまでの整数を処理して素数判定を行いますが、実際は、素数かどうかを判定したいある整数nの√n以下の素数たちまで割り算をすればよいです。

なぜならnが合成数なら必ず√nより小さい素因数を持つからです。

例えば 31 が素数かどうか判定するときに 5<√31<6 なので 5 以下の素数で割り切れないことを証明すればOKです。つまり「2 の倍数でない，3 の倍数でない，5 の倍数でない」ことを確認すればOKです。以下実装手順です。

# 処理回数を減らす
def judge_prime_num_p2(int_num):
    for i in range(2, int(math.sqrt(int_num))+1):
        if int_num % i == 0:
            print("{0} is composite".format(int_num))
            return

    print("{0} is Prime".format(int_num))

if __name__ == "__main__":
    judge_prime_num_p2(31)

Terminalでの実行結果

# 実行結果
31 is Prime

##P3：エラトステネスのふるい
最後にエラトステネスのふるいというアルゴリズムを使用して素数判定を行ってみたいと思います。P1のようなアルゴリズムに比べてエラトステネスのアルゴリズムは処理が早いことが知られています。
エラトステネスのふるいとその計算量

エラトステネスのふるいのアルゴリズムは以下の手順になります。
1：2 から n までの整数を並べる。
2：生き残っている数の中で一番小さい（かつまだ p として使われていない）ものを新たに p とおき，p 以外の p の倍数を全て消していく。
3：2の操作を繰り返していき，p が n−−√ を越えたら終了。最終的に生き残ったものが素数。

# エラトステネスのふるい
def judge_prime_num_p3(int_num):

    # 2からint_numまでの整数群
    num_list = [i for i in range(2, int_num+1)]

    # ふるいにかける値
    p = min(num_list)

    # ふるいにかけた値を格納しておくリスト
    p_list = []

    while int(math.sqrt(int_num))+1 > p:
        # ふるいにかける値をリストに格納
        p_list.append(p)

        # pの倍数を整数リストから除外
        for i in num_list:
            if i % p == 0:
                num_list.remove(i)
        
        p = min(num_list)  # 次にふるいにかける値を更新

    # 素数リスト
    num_list.extend(p_list)
    num_list.sort()
    print("Prime(2 to {0}): {1})".format(int_num, num_list))

if __name__ == "__main__":
    judge_prime_num_p3(31)

Terminalでの実行結果

# 実行結果
Prime(2 to 31): [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31])

今回は素数判定のいろいろなアルゴリズムの実装を行ってみました。
良いPythonの復習になったと思います。(笑)

参考

素数判定いろいろ - シンプルな判定と、素数の分布