素数判定のアルゴリズムとライブラリ【Python】

素数判定のアルゴリズムをPythonで実装する方法を紹介していきますが、その前に計算量の比較を紹介しておきます

試し割り法(めちゃくちゃ簡単)

おそらく最も簡単な素数判定のプログラムですね

単純に自分より小さい数で割ってみて、割れなかったら素数と判定します

def isPrime(n):
    for i in range(2, n):
        if n%i==0:
            return False
    if n==1:
        return False

    return True

for i in range(2,100):
    print(i,':',isPrime(i))

試し割り法の改善

試し割り法は愚直に割って言っているだけなので、いくつか改善する点がありそうです

今回は以下の改善を行います

\(\sqrt{n}\)までしか判定しなくて良い
偶数は必ず割り切れるので、2以外の偶数は必ず素数でない(奇数のみ判定する)

ちなみに1個目の改善点がわからなければ、以下を参考にしてください

次の問題の解き方を教えて下さい自然数nが，√n（ルートnです）以下のすべての素数で割り切れなければ，nは素数であることを... - Yahoo!知恵袋

次の問題の解き方を教えて下さい自然数nが，√n（ルートnです）以下のすべての素数で割り切れなければ，nは素数であることを照明せよ。です。それと，自分にはさっぱりなのですがこの問題はどれくらいの難しさなのでしょうか？約数をさがす作業、やったことありますか？例えば、60の約数は何個あるか、といわれたとき、1,2,3,4...

import math

def isPrime(n):
    for i in range(3, math.floor(math.sqrt(n))+1, 2):
        if n%i==0:
            return False

    if n==2:
        return True
    if n%2==0:
        return False
    if n==1:
        return False

    return True

for i in range(2,100):
    print(i,':',isPrime(i))

エラトステネスの篩

エラトステネスの篩はエラトステネスさんが考えた素数判定のアルゴリズムです
素数判定ではよく使われるのではないでしょうか？

エラトステネスの篩は表を使って素数を求めます
例えば37以下の素数を全て求めたければ、以下のような表を作ります

そしたら小さい数字から見ていくのですが、まず2は表にあるから(ふるい落とされていない)素数となります
素数の倍数は素数ではないので、2の倍数を表から消していきましょう

次に3に対しても同じことを行います

これを\(\sqrt{37}\)まで繰り返していきましょう
そしてその表がこれです

最終的には表には素数しか残っていないはずです

このエラトステネスの篩をPythonコードに落とすと以下のようになります
あっていると思いますが、自前コードなので間違えてたら教えてください

import math

# n以下の素数判定のリストを返す(0は簡単にするために入れているだけです)
def eratosthenes(n):
    prime_list = [False, False] + [True]*(n-1)
    for i in range(2, math.floor(math.sqrt(n))+1):
        if not prime_list[i]:
            continue
        for j in range(i*2, n+1, i):
            prime_list[j] = False
    return prime_list

n = 10
l = eratosthenes(n)
for i in range(n+1):
    print(i,':',l[i])

# 0 : False
# 1 : False
# 2 : True
# 3 : True
# 4 : False
# 5 : True
# 6 : False
# 7 : True
# 8 : False
# 9 : False
# 10 : False