素数の判定（試し割り法）

　プログラミングコンテストでは素数に関する問題が出されることが多々あります。今回は、ある自然数 n が素数であるかどうかを判定するアルゴリズムの一つである試し割り法を紹介します。

素数とは？

　まずは“素数”についての確認をしていきます。素数とは、1より大きく、1とその数以外に約数を持たない整数のことです。例えば “2” は、 “1” と自分自身である “2” のみで割り切れるので素数ですが、”4″ は “1” 、”2″ および “4”で割り切れるので素数ではありません。

試し割り法

　試し割り法は、ざっくり言えば、対象とする数 n より小さな数で割り算を行ってみて、”1″ 以外で割り切ることができたら素数ではない、割り切れなかったら素数である、と判定する方法です。
　以上の方法をそのままプログラムで実装すると、n が大きな数の場合、計算量がとても多くなります。そこで実際には試し割りする数は √n までで良いという性質を利用して計算量を減らします（詳細については他のサイトを検索してご参照下さい…）。

python3での実装

実装例を n = 47 の場合を例に以下に示します。

import math  #sqrt を使用するので math をインポート
 
n = 47
 
def check_prime_number(number):

    check_range = int(math.sqrt(number))  # √n
 
    for i in range(2,check_range+1):  # 1は試す必要がないので2から
                                      # また、forループの終わりはcheck_rangeにしたいので +1
        #1とn自身以外の数で割り切れたら 素数ではないので False を返す
        if number % i == 0:
            return False
    # 割り切れる数がない場合は素数なので True を返す
    return True
 
print(check_prime_number(n))
# --> True

以上がpython3で、試し割り法により素数を判定する方法になります。