【超入門】高速に素数判定する方法とアルゴリズムを解説！ Pythonでの実装

そまちょブログのそまちょ（@somachob）です。

競技プログラミングや数学の分野で、素数判定は非常に重要なテーマの1つです。

しかし、全探索では計算量が膨大になり、現実的な時間内に解決することはできません。

本記事では、Pythonを使って高速に素数判定するためのアルゴリズムを紹介します。

初心者でも理解しやすく、エラトステネスのふるいを使ったアルゴリズムを中心に詳しく解説します。

素数とは何か
素数判定の基本的なアルゴリズム
1. 全探索による素数判定
2. 実行時間と計算量の問題点
高速な素数判定アルゴリズム
1. エラトステネスのふるい
まとめ
参考

素数とは何か

素数とは、1とその数自身以外の正の整数で割り切れない数のことです。

例えば、2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31などが素数になります。

4 や 6 のような数は 2 で割り切れます。このような、1 とその数自身以外の正の整数で割り切れる数は合成数と呼ばれます。

素数は、数学の中でも重要な概念であり、暗号理論やコンピューターセキュリティーなど、多くの分野で利用されています。

例えば、RSA暗号のような公開鍵暗号方式では、素数の探索や素数の乗算が必要になります。

素数判定の基本的なアルゴリズム

素数判定アルゴリズムの基礎的な手法について説明します。

最も単純なアルゴリズムである全探索による素数判定方法を取り上げ、その問題点を説明します。

全探索による素数判定

素数判定の基本的なアルゴリズムは、全探索による方法です。

素数を判定するために、全ての自然数を1から順番に調べる方法を全探索法と呼びます。

ある数 n が素数であるかどうかを判定するには、n を 2 から n-1 までの全ての自然数で割ってみて、割り切れる数があるかどうかを確認するという方法です。

以下は、Pythonで実装したコード例です。

# 素数判定
def is_prime(n):
    # 1 未満の数は素数ではない
    if n < 2:
        return False
    
    # n までの数について割り切れる数があるか判定
    for i in range(2, n):
        # 割り切れる数がある場合、素数ではない
        if n % i == 0:
            return False

    # 割り切れる数がない場合、素数である
    return True

素数は、1 とその数自身以外の正の整数で割り切れない数のことなので、それを実装しています。

引数 n が 2 より小さいときは、False を返します。

次に、2 から n-1 までの正の整数 i で n が割り切れるかどうかを調べています。

もし、n を割り切れる i があれば、False を返します。

最後に、2 から n-1 までのどの数でも割り切れなければ、True を返します。

たとえば、59 が素数か判定するときのコードは次のようになります。

# 素数判定
def is_prime(n):
    if n < 2:
        return False

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

    return True


if is_prime(59):
    print('59 は素数です')
else:
    print('59 は素数ではありません')


"""実行結果
59 は素数です
"""

この方法は、最も単純で分かりやすいアルゴリズムですが、計算量が大きいため、n が大きくなると処理に時間がかかるという問題があります。

実行時間と計算量の問題点

全探索法による素数判定の計算量は、n が素数の場合、最大で約 n 回の除算が必要になります。

全探索による素数判定の計算量は O(n) となります。

n が大きい場合には非常に時間がかかってしまいます。たとえば、n が 10⁹ 程度のときには、約10億回の割り算を行う必要があります。

このアルゴリズムでは、判定する数が大きくなるにつれて、処理に時間がかかるため、高速なアルゴリズムが必要になります。

高速な素数判定アルゴリズム

n が合成数（素数でない数）のとき、2 から √n までの数で割り切れるかどうかを確認すればよいことが知られています。

つまり、n が素数かを調べるときは、n-1 まで調べる必要はなく、√n までの自然数で割り切れる数があるかどうか確認するだけで済みます。

n が 10⁹ 程度のとき、全探索だと約10億回の割り算が必要でしたが、この方法だと約３万回の割り算で済みます。

この方法は全探索に比べて効率的であり、高速な素数判定アルゴリズムの基礎となっています。

以下は、2 から √n までの整数で割ることで、n が素数かどうかを判定するコードです。n**0.5 は、累乗を計算するので n の 0.5 乗、つまり √n を表します。

# 素数判定
def is_prime(n):
    if n < 2:
        return False

    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False

    return True

この素数判定の計算量は O(√n) となります。

たとえば、59 が素数か判定するには、全探索のときだと 2 から 58 まで割り算する必要がありましたが、この方法では２から 7 まで割り算をするだけで済みます。

エラトステネスのふるい

エラトステネスのふるいは、素数を見つけるための効率的なアルゴリズムの一つです。

このアルゴリズムは、ある自然数 n までの全ての素数を見つけることができます。

このアルゴリズムを簡単に説明すれば、次の手順のようになります。

2 から n までの自然数を並べる。
最小の 2 を残して、2 の倍数をすべて取り除く。
残った数の最小の 3 を残して、3 の倍数をすべて取り除く。
残った数の最小の 5 を残して、5 の倍数をすべて取り除く。
以下同様に、まだ消えてない最小の数を残し、その倍数をすべて取り除く。
残った数の最小が √n を超えたら、残った数はすべて素数。

以下に、エラトステネスのふるいの Python でのコードを示します。

def eratosthenes(n):
    # n までの自然数を列挙する
    isPrimes = [True] * (n+1)

    # 0 と 1 を取り除く
    isPrimes[0], isPrimes[1] = False, False

    # 2 から √n まで繰り返す
    for i in range(2, int(n**0.5)+1):
        # i が取り除かれていないとき
        if isPrimes[i]:
            # i の倍数を取り除く
            for j in range(2*i, n+1, i):
                isprimes[j] = False

    # 2 から n までの素数のリストを返す
    return [i for i in range(2, n+1) if isPrimes[i]]

このアルゴリズムの計算量は、O(n log log n) です。

エラトステネスのふるいは、競技プログラマーにとって非常に役立ちます。

例えば、n 以下の素数がいくつあるのかを求めたり、n 以下の素数を列挙する問題などに使うことができます。

次のコードは、50 までの素数を出力します。

def eratosthenes(n):
    # n までの自然数を列挙する
    isPrimes = [True] * (n+1)

    # 0 と 1 を取り除く
    isPrimes[0], isPrimes[1] = False, False

    # 2 から √n まで繰り返す
    for i in range(2, int(n**0.5)+1):
        # i が取り除かれていないとき
        if isPrimes[i]:
            # i の倍数を取り除く
            for j in range(2*i, n+1, i):
                isPrimes[j] = False
    return [i for i in range(2, n+1) if isPrimes[i]]


print(eratosthenes(50))


"""実行結果
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
"""