Pythonで学ぶ！素数判定のアルゴリズムとその実装方法

素数とは何か：定義と性質

素数とは、1と自分自身以外の約数を持たない正の整数のことです。例えば、2、3、5、7、11、13などが素数です。一方、4、6、8、9、10などは素数ではありません。

素数には以下のような性質があります。

  • 2以外の偶数は素数ではありません。
  • 素数は無限に存在します。
  • 2以上の整数は、必ず素数と合成数のいずれかに分類されます。

素数判定の基本的なアルゴリズム：試し割り法

素数判定の基本的なアルゴリズムとして、「試し割り法」があります。試し割り法は、判定対象の数を2から順番に割っていくことで、その数が素数かどうかを判定する方法です。

Pythonでの試し割り法の実装例を以下に示します。

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
print(is_prime(2))  # True
print(is_prime(4))  # False
print(is_prime(7))  # True

上記のコードでは、is_prime関数に判定対象の数nを渡すことで、その数が素数かどうかを判定しています。試し割り法では、2からnの平方根までの数で割り切れるかどうかを調べます。もし割り切れる数があった場合は、nは素数ではなく合成数と判断します。

Pythonでの試し割り法の実装方法

Pythonでの試し割り法の実装方法について説明します。

  1. 判定対象の数nを受け取る。
  2. nが2未満の場合は、Falseを返す。
  3. 2からnの平方根までの数で順番に割っていく。
  4. もし割り切れる数があった場合は、Falseを返す。
  5. 割り切れる数がなかった場合は、Trueを返す。

素数判定の効率的なアルゴリズム：エラトステネスの篩

試し割り法では、判定対象の数が大きくなると、計算量が膨大になってしまいます。そこで、より効率的な素数判定アルゴリズムとして、「エラトステネスの篩」があります。

エラトステネスの篩は、2からnまでの数のうち、素数であるものを順番に取り出しながら、その倍数を削除していくという方法です。最終的に残った数が素数となります。

Pythonでのエラトステネスの篩の実装例を以下に示します。

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, False
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i ** 2, n + 1, i):
                is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
print(sieve_of_eratosthenes(20))  # [2, 3, 5, 7, 11, 13, 17, 19]

上記のコードでは、sieve_of_eratosthenes関数に判定対象の数nを渡すことで、2からnまでの素数のリストを返します。is_primeリストに、Trueを初期値として設定し、素数でない数はFalseに変更していくことで、最終的に残った数が素数となります。

Pythonでのエラトステネスの篩の実装方法

Pythonでのエラトステネスの篩の実装方法について説明します。

  1. 判定対象の数nを受け取る。
  2. 2からnまでの数について、素数であるかどうかを管理するis_primeリストを作成する。
  3. is_primeリストの0と1をFalseに設定する。
  4. 2からnの平方根までの数で順番に取り出し、素数であるものについて、その倍数をFalseに変更する。
  5. is_primeリストのTrueになっている数を素数として返す。

素数判定のさらなる高速化：ミラー・ラビン法

エラトステネスの篩でも十分に高速な素数判定が可能ですが、より高速な素数判定アルゴリズムとして、「ミラー・ラビン法」があります。

ミラー・ラビン法は、判定対象の数が素数である確率を高精度に計算する方法です。判定対象の数nが素数である確率が高いほど、判定が早く終了します。

Pythonでのミラー・ラビン法の実装例を以下に示します。

import random
def is_prime(n, k=5):
    if n == 2 or n == 3:
        return True
    if n < 2 or n % 2 == 0:
        return False
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for i in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for r in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True
print(is_prime(2))  # True
print(is_prime(4))  # False
print(is_prime(7))  # True

上記のコードでは、is_prime関数に判定対象の数nと、繰り返し回数kを渡すことで、その数が素数かどうかを判定しています。ミラー・ラビン法では、n-1を2の累乗で表すことで、nが素数である確率を高精度に計算します。

まとめ

Pythonでの素数判定アルゴリズムとその実装方法について解説しました。試し割り法やエラトステネスの篩は、シンプルかつ高速なアルゴリズムです。ミラー・ラビン法は、より高精度な素数判定が必要な場合に使用します。