Pythonで学ぶ素数判定アルゴリズム入門：試し割り法・エラトステネスの篩・ミラーラビン法
このページでは、Pythonを使って素数判定を行う代表的なアルゴリズムをまとめて解説します。
対象読者は、入社1〜3年目くらいのPythonエンジニアを想定しています。
「とりあえず動けばOK」から一歩進んで、計算量やアルゴリズムの使い分けまで意識できるようになることをゴールにしています。
この記事では、次の3つのアルゴリズムを扱います。
- 最も素直な方法：試し割り法
- 多数の素数をまとめて列挙したいとき：エラトステネスの篩
- 巨大な数を高速に判定したいとき：ミラー・ラビン法（確率的アルゴリズム）
素数とは何か：定義と性質
素数（prime number）とは、1と自分自身以外に約数を持たない 2 以上の自然数のことです。
例えば、2、3、5、7、11、13 などは素数です。一方、4（= 2 × 2）、6（= 2 × 3）、8（= 2 × 4）、9（= 3 × 3）、10（= 2 × 5）などは、1と自分自身以外にも約数を持つので合成数と呼ばれます。
素数には、次のような基本的な性質があります。
- 2 以外の偶数は素数ではありません（必ず 2 で割り切れる）。
- 素数は無限に存在することが数学的に証明されています。
- 2 以上の整数は、必ず素数または合成数のいずれかに分類されます。
実務目線で言うと、素数や素因数分解は、暗号技術（RSA など）やハッシュ関数の設計、乱数生成など、エンジニアの仕事と意外と近い領域でも使われています。
素数判定アルゴリズムの全体像
素数判定アルゴリズムは、大きく次の2パターンに分けられます。
- 1つの数が素数かどうかを判定するアルゴリズム（試し割り法、ミラー・ラビン法など）
- ある範囲内の素数をすべて列挙するアルゴリズム（エラトステネスの篩など）
どのアルゴリズムも「正しさ」がもちろん重要ですが、実務や競技プログラミングではそれに加えて計算量（時間計算量）がかなり効いてきます。
この記事では、それぞれのアルゴリズムについて Python のコードとあわせて、簡単な計算量・使いどころも整理していきます。
試し割り法：最も基本的な素数判定アルゴリズム
試し割り法の考え方
試し割り法は、ある整数 n が与えられたときに、
2 から √n までの整数で順番に割ってみて、どれでも割り切れなければ素数とみなす
という非常に素直な方法です。
なぜ √n まで見れば十分かというと、もし n が合成数なら、
n = a × b を満たす 2 以上の整数 a, b が存在します。
そのとき、a と b のどちらかは必ず √n 以下になるため、√n まで調べれば「割り切れる相手」を見つけられる、という理屈です。
Python での試し割り法の実装例
def is_prime_trial_division(n: int) -> bool:
"""試し割り法による素数判定。
:param n: 判定対象の整数
:return: n が素数なら True、それ以外なら False
"""
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
# 2 以外の偶数は素数ではない
return False
# 3, 5, 7, ... と奇数だけを試し割りする
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
if __name__ == "__main__":
print(is_prime_trial_division(2)) # True
print(is_prime_trial_division(4)) # False
print(is_prime_trial_division(7)) # True
print(is_prime_trial_division(97)) # True
試し割り法の計算量と使いどころ
試し割り法の時間計算量は、おおよそ O(√n) です。
n がそこまで大きくなければ（例えば 109 程度まで）、実務でも十分使えるケースがあります。
ただし、同じような判定を大量に繰り返す場合や、n が非常に大きくなる場合には、より効率的な方法を検討した方がよく、その代表例が次に紹介するエラトステネスの篩です。
エラトステネスの篩：範囲内の素数をまとめて列挙する
エラトステネスの篩の考え方
エラトステネスの篩は、2 ～ n までの素数を一気に求めたいときに非常に強力なアルゴリズムです。
手順は次のようになります。
- 2 ～ n の整数を「とりあえず全部、素数候補」として持つ。
- 2 から順に、まだ「素数候補」と残っている数 p を見つける。
- p の倍数（2p, 3p, 4p, …）を「素数ではない」として候補から削除する。
- p が √n を超えるまで 2, 3, 5, … と繰り返す。
- 最後まで残った数が素数になる。
一つ一つの数を独立に判定するよりも、多数の素数をまとめて求めるのに向いているアルゴリズムです。
Python でのエラトステネスの篩の実装例
from typing import List
def sieve_of_eratosthenes(n: int) -> List[int]:
"""エラトステネスの篩で 2 ～ n の素数を列挙する。
:param n: 上限値（2 ～ n の素数を求める）
:return: 素数のリスト
"""
if n < 2:
return []
# is_prime[i] が True なら i は素数候補
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False
# √n までの素数候補について倍数をふるい落とす
i = 2
while i * i <= n:
if is_prime[i]:
# i の 2 乗以上の倍数を削除していく
j = i * i
while j <= n:
is_prime[j] = False
j += i
i += 1
return [i for i in range(2, n + 1) if is_prime[i]]
if __name__ == "__main__":
print(sieve_of_eratosthenes(20)) # [2, 3, 5, 7, 11, 13, 17, 19]
エラトステネスの篩の計算量と注意点
エラトステネスの篩の時間計算量は、おおよそ O(n log log n) と言われており、かなり高速です。
ただし、0 ～ n の配列を丸ごと持つため、空間計算量は O(n) になります。
そのため、
- n が数億レベルになると、メモリ使用量もそれなりに大きくなる
- 「1つの n が素数かだけ知りたい」ときには、試し割り法やミラー・ラビン法の方が向いている
といったトレードオフがあります。
競技プログラミングや CP 系のタスクで「1 ～ N の素数を全部使いたい」といったときに非常によく使われる手法です。
ミラー・ラビン法：巨大数向けの確率的素数判定
ミラー・ラビン法の特徴
ミラー・ラビン法は、確率的素数判定アルゴリズムの一つです。
「確率的」という名前の通り、理論的にはごくまれに「合成数なのに素数と判定してしまう（偽陽性）」ケースがありますが、
繰り返し回数 k を適切に増やしていけば、その確率を現実的には無視できるレベルまで小さくできます。
巨大な整数（桁数が非常に大きい n）を扱うときや、暗号関連のアルゴリズムなどでは、このような確率的アルゴリズムが実務でもよく使われます。
ミラー・ラビン法の Python 実装例
import random
def is_prime_miller_rabin(n: int, k: int = 5) -> bool:
"""ミラー・ラビン法による確率的素数判定。
:param n: 判定対象の整数
:param k: テスト回数（大きいほど誤判定確率が下がる）
:return: n が「ほぼ確実に」素数なら True、合成数と判定された場合は False
"""
# 2, 3 は素数として扱う
if n == 2 or n == 3:
return True
# 2 未満、偶数は素数ではない
if n < 2 or n % 2 == 0:
return False
# n - 1 を 2^s * d の形に分解する
d = n - 1
s = 0
while d % 2 == 0:
d //= 2
s += 1
# ランダムに a を選んでテストを k 回繰り返す
for _ in range(k):
a = random.randint(2, n - 2)
x = pow(a, d, n)
if x == 1 or x == n - 1:
# この a ではまだ合成数と断定できない
continue
is_witness = True
for _ in range(s - 1):
x = pow(x, 2, n)
if x == n - 1:
# まだ合成数と断定できない
is_witness = False
break
if is_witness:
# a が n の合成性の「証人」になった
return False
# k 回のテストをすべてパスしたので、かなりの高確率で素数とみなす
return True
if __name__ == "__main__":
print(is_prime_miller_rabin(2)) # True
print(is_prime_miller_rabin(4)) # False
print(is_prime_miller_rabin(7)) # True
print(is_prime_miller_rabin(97)) # True
ミラー・ラビン法の計算量と扱い方
ミラー・ラビン法は、1 回のテストあたりおおよそ O(log³ n) 程度と言われることが多く、
試し割り法（O(√n)）と比べて、n が十分大きくなるほど有利です。
一方で、100 桁レベルの巨大な n を扱わない場合や、そこまで極端なパフォーマンスを求めない場合には、
実装コストとのバランスで「まずは試し割り法でも十分」というケースも多いです。
アルゴリズムの使い分けガイド
ここまで見てきた3つのアルゴリズムを、ざっくりと「どういう場面で使うか」という目線で整理しておきます。
-
試し割り法：
- 1回ごとの判定対象がそこまで大きくない（例：109 前後まで）
- 実装をシンプルに保ちたい
- まずはアルゴリズム学習の入り口として理解したい
-
エラトステネスの篩：
- 1 ～ N までの素数を全部欲しい
- 繰り返し素数を使う処理が多い
- 競技プログラミングなどで N の上限が明示されている
-
ミラー・ラビン法：
- 非常に大きな数の素数判定をしたい
- 暗号系の処理やライブラリ実装など、高速な判定が必要
- わずかな確率の誤判定を許容できる（または、他のチェックと組み合わせる）
よくある質問（FAQ）
Q. 実務でとりあえず素数判定したいとき、どれを使えば良いですか？
判定対象の整数がそこまで大きくなく、件数もそれほど多くないなら、まずは試し割り法で十分なことが多いです。
パフォーマンスに不満が出てきたら、範囲や用途に応じて、エラトステネスの篩やミラー・ラビン法を検討すると良いと思います。
Q. ミラー・ラビン法は「確率的」と聞くと怖いのですが、大丈夫でしょうか？
厳密には「ごくまれに合成数を素数と誤判定する可能性」がありますが、
テスト回数 k をそこまで大きくしなくても、現実的な用途では誤判定確率をほぼ無視できるレベルまで下げることができます。
実務では、他のチェック方法と組み合わせたり、安全側に倒した設計にすることでリスクをさらに抑えることが多いです。
Q. エラトステネスの篩はメモリをたくさん使うと聞きました。
その通りで、n に比例した配列を 1 つ持つので、空間計算量は O(n) です。
とはいえ、例えば n = 107 くらいまでなら、Python でも工夫次第で実用範囲になることが多いです。
n がさらに大きくなってきたら、区間篩（セグメント木のようなイメージで範囲を分割して処理する方法）など、もう一段階進んだ方法もあります。
まとめ
このページでは、Python による素数判定アルゴリズムとして、試し割り法、エラトステネスの篩、ミラー・ラビン法を紹介しました。
- まずは試し割り法で素数判定の基本的な考え方に慣れる。
- 範囲内の素数をたくさん使いたいときはエラトステネスの篩を使う。
- 巨大な整数を相手にするときはミラー・ラビン法のような確率的アルゴリズムも選択肢。
アルゴリズムそのものを覚えるだけでなく、「どの場面でどれを選ぶか」を意識できるようになると、
実務でのパフォーマンスチューニングや設計判断にも活きてきます。
ぜひ、実際にコードを書いてベンチマークを取ってみたり、自分なりに改良してみたりしながら、理解を深めてみてください。
![[Python]関数を返すreturnの使用法と応用例 コードで理解しよう](https://machine-learning-skill-up.com/knowledge/wp-content/uploads/2023/12/1-1404.jpg)