Pythonで素数判定機械を作ろう

16桁程度の大きい数でも20秒もかからず判定してくれます。また、その数の正の約数をすべて表示するモードかただ素数を判定するだけか選ぶことができます。
ページの最後にコードを載せたのでコピペ等で自由にご使用ください。

そもそも素数とは

プログラムを作る前に、そもそも"素数"がどのような数かを復習しておきましょう。
素数とは、正の約数が1とその数自身の2つしかない自然数のことです。2,3,5,7,11,13,17,19,…と続き、無限に存在することがわかっています。よくある間違いですが1は素数ではありません。1は正の約数が自身の1つしかない数なので、素数の定義からは外れます。

素数判定のメカニズム

ある数$${n}$$が素数かどうかを判定する方法はいくつかありますが、今回はあまり複雑な定理などは使わずに単純な下の方法を使ってプログラムを組みます。

「ある数$${n}$$が素数のとき、$${n}$$は$${\sqrt{n}}$$以下のすべての素数で割り切ることができない」

言い換えれば、$${\sqrt{n}}$$以下の数のどれか1つでも$${n}$$を割り切ることができれば、$${n}$$は素数ではないということです。

機能を増やす

素数を判定するとき、基本的には割り切れた瞬間判定終了で大丈夫です。しかし、割り切れた数を記録しておくことで、約数表示機械としても使えます。そのためには、$${\sqrt{n}}$$までではなく、$${\frac{n}{2}}$$まで処理をする必要があります。しかし、普通に判定するだけではこれはやりすぎなので、モードを分けて$${\frac{n}{2}}$$まで判定するかしないかを入力時に変えられるようにします。

プログラムコード

ここでは結構しっかり仕組みを解説します。まずはコードを載せておきます。

import math

def m(n,mode):
    print()
    n = int(n)
    mode = int(mode)
    nlist = []
    numbers = 1
    flag = True
    for m in range(2,int(n/2+2)):
        if mode == 2 and m > (math.sqrt(n)+1):
            flag = True
            break
        if n % m == 0:
            flag = False
            nlist.append(m)
            if mode == 2:
                break
    nlist.append(n)
    if n == 2:
        flag = True
        nlist = [2]
    if flag == True:
        print("%sは素数です。" % n)
    else:
        print("%sは素数ではありません。" % n)
        if mode == 2:
            print("少なくとも%sで割り切れます。" % nlist[0])
    if mode == 1:
        print("%sの正の約数は下の通りで、%s個あります。" % (n,len(nlist)+1))
        for i in nlist:
            numbers = ("%s,%s" % (numbers,i))
        print(numbers)
    print()

def n():
    try:
        input_n = int(input("2以上の自然数を半角数字で入力してください>>>"))
        if input_n < 2:
            error
        input_mode = int(input("""
モードを下から選択して半角数字で入力してください
1:その数が素数かどうかを判定し、またその数の正の約数をすべて出力します。
2:その数が素数かどうかのみを判定して出力します。こちらのほうが動作は早いです。
>>> """))
        if input_mode != 1 and input_mode != 2:
            error
        m(input_n,input_mode)
    except:
        print("指定以外の数または大きすぎる数が入力されました。入力し直してください。")
        return

print("""n() と入力してEnterキーを押すと素数判定プログラムが起動します
""")        

まずm関数ですが、これは引数にnとmodeを持ちます。nは入力された数、modeは$${\frac{n}{2}}$$まで判定するか否かを示しています。mode=1なら$${\frac{n}{2}}$$,mode=2なら$${\sqrt{n}}$$までの判定ということです。その下のfor文で$${2}$$から$${\frac{n}{2}}$$または$${\sqrt{n}}$$までの数を1つずつ変数に割り当てて、それがnを割り切れるかを調べます。mode=1なら、割り切れた数をリストに記録します。mode=2であれば、割り切れたときに判定を終了したいので、breakでループを抜け出します。また、割り切れたときに素数かどうかを示す変数flagをFalseにします。そして、そのあとでmodeに合った出力を表示します。

n関数は、そこまで複雑なものではなく、入力を受け取ってm関数に渡しているだけです。try-except構文で2以上の自然数が入力されなかったときにPythonのわかりにくいエラーを出さずにメッセージを表示するようにしています。input_nやinput_modeの下のif分の中にある「error」というコードは、指定以外の数をm関数に渡さないためにわざとエラー処理を起こさせるために書いています。

この素数判定機械は単純な方法でプログラムを組んでいるので、10桁周辺くらいなら動作が速いと思いますが、大きい桁を入力しすぎると多少動作が遅くなってしまいます。m関数を改造すればフェルマーの小定理などを使用しての判定などもできるので、ぜひ改造してみてください！