Pythonで素数判定を行うプログラミング方法を初心者向けに実例6選で解説

Pythonで素数判定を学ぶと、割り算の余り、条件分岐、繰り返し、計算量の考え方を同時に整理できます。素数は数学だけの題材ではなく、プログラミングでアルゴリズムを比較する入口にもなります。

この題材で特に押さえたいのは、n % i == 0で割り切れるかを調べ、math.isqrt()で平方根までの探索に抑え、範囲列挙ではエラトステネスの篩を使い分ける点です。そのため、シンプルなコーディングから最適化まで段階的に理解できるのが基本です。

素数とは？

素数とは、1より大きい自然数のうち、1とその数自身以外の正の約数を持たない数です。その定義をPythonの素数判定に落とし込むと、2以上の候補で割り切れるかを調べる問題になります。

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

結果: 期待される表示は、100未満にも複数の素数が並ぶ形です。

これらの数は、2で割れる偶数や3で割れる倍数とは違い、途中の整数で割り切れません。数学の定義としては単純でも、プログラミングではif、for、range()、returnをどう組み合わせるかが読みやすさに直結します。

その性質は暗号理論や数論の基礎にも関係しますが、初心者の学習では余りを求める%演算子の理解が出発点です。例えば12 % 3は0になり、12 % 5は2になるため、前者は割り切れ、後者は割り切れないと判断できるのが目安です。

ただし、素数判定で1を素数として扱ってはいけません。1は正の約数が1個だけであり、1とその数自身という二種類の約数を持つという条件を満たさないためです。

このとき、判定対象をnと置くと、n <= 1は最初に除外できるのが基本です。2は最小の素数であり、2以外の偶数はn % 2 == 0で合成数と分かります。

一般に、ある数nがa * bで表せるなら、aかbの少なくとも一方はsqrt(n)以下になるのがポイントです。そのため、2からn - 1まで全て試すより、平方根までで止めるほうが自然なアルゴリズムになります。

💡 Tips: Python公式ドキュメントでは、整数平方根を返す関数としてmath.isqrt()が説明されているのが目安です。浮動小数点数を経由しないため、大きな整数の素数判定で扱いやすい選択肢になるのが一般的です。

素数判定の基本

基本的な素数判定では、nが1以下ならFalse、割り切れる約数が見つかればFalse、最後まで見つからなければTrueを返します。この流れは数学の定義をそのまま条件分岐に写したものです。

その流れをコーディングするときは、判定の順番にも意味があります。先に小さい例外値を処理し、そのあとでループに入ると、関数全体の読み筋が短くなるのが現実的です。

from math import isqrt

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, isqrt(n) + 1):
        if n % i == 0:
            return False
    return True

結果: 期待される動作は、nが素数ならTrue、合成数または1以下ならFalseを返すことです。

これでisqrt(n) + 1までをrange()の終端にしているのは、range()が終端値を含まないためです。例えばnが49なら平方根は7なので、7で割る検査まで含める必要があります。

一方、n**0.5を使う書き方も見かけますが、結果がfloatになる点には注意が必要です。小さな整数では問題が表に出にくいものの、大きな整数を扱う数学寄りのプログラミングではmath.isqrt()のほうが堅実です。

初心者向けのシンプルな素数判定法

シンプルな素数判定法は、定義を理解する目的に向いています。効率よりも読みやすさを優先し、2からn - 1までを調べると、割り切れる数を探す処理の意味が見えやすくなると整理できるのがポイントです。

具体的には、for i in range(2, n)で候補の約数を順番に取り出し、n % i == 0なら合成数と判断します。この書き方は計算量の面では遠回りですが、素数判定の初学者には条件の対応関係が分かりやすい形です。

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

print(is_prime_simple(1))
print(is_prime_simple(2))
print(is_prime_simple(3))
print(is_prime_simple(4))
print(is_prime_simple(11))

結果: 期待される出力は、False、True、True、False、Trueの順です。

このコードでは、2を渡したときにrange(2, 2)が空になります。そのためループ内のreturn Falseは実行されず、最後のreturn Trueに到達します。

その挙動を理解すると、空の範囲、早期リターン、条件式の評価順も同時に学べますし、ここがポイントです。プログラミングでは、関数がどの行で終了するかを追う習慣がコーディングの読み間違いを減らするのが一般的です。

ただし、range(2, n)のままだと、nが大きいほど割り算の回数が増えます。例えば1000003のような大きめの素数候補では、途中で割り切れない限り多数の候補を調べることになると理解できます。

この課題はアルゴリズムの選び方で解決できるのが現実的です。定義確認には単純版、通常の判定には平方根版、範囲列挙には篩という使い分けが現実的です。

読みやすい関数名と戻り値

関数名はis_primeやis_prime_simpleのように、真偽値を返すことが分かる形にすると読みやすくなると覚えるとよいでしょう。その名前を見れば、戻り値がbool型のTrueまたはFalseだと予想できます。

これに対して、素数の一覧を返す関数はlist_primesやprimes_in_rangeのような名前が合いると整理できます。戻り値の種類を名前に反映すると、あとからコードを読むときの負担が下がりますが、これは押さえたい点です。

基本的に、判定関数は単一の数を受け取り、一覧生成関数は範囲を受け取ります。この役割を混ぜるとテストしづらくなるため、関数を小さく保つ設計が扱いやすいと言えるでしょう。

効率的な素数判定アルゴリズム

効率的な素数判定アルゴリズムでは、無駄な約数候補をどれだけ減らせるかが焦点になります。平方根までで止め、2以外の偶数を除外すると、単純な全探索より少ない計算で済みますし、これが一つの目安です。

この改善は数学の性質に基づいていると理解できます。合成数の因数ペアには小さい側の因数が必ず存在するため、大きい候補を後ろまで調べ続ける必要がありません。

from math import isqrt

def is_prime_fast(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, isqrt(n) + 1, 2):
        if n % i == 0:
            return False
    return True

for value in [1, 2, 3, 4, 5, 100, 101]:
    print(value, is_prime_fast(value))

結果: 期待される出力は、1と4と100がFalse、2と3と5と101がTrueになる組み合わせです。

そのコードでは、if n == 2を偶数判定より前に置いています。順番を逆にすると、2もn % 2 == 0に該当してFalseになってしまうためです。

このとき、range(3, isqrt(n) + 1, 2)の第三引数2は、奇数だけを調べるための増分です。2で割れない数について、4、6、8のような偶数候補を試す意味はありません。

一方、単一の数を調べるならこの関数で十分な場面が多いですが、1から100000までの素数一覧を得たい場合は話が変わります。各数に対してis_prime_fast()を呼ぶより、範囲全体をまとめて処理するアルゴリズムが向いていると考えられますし、ここがポイントです。

エラトステネスの篩

エラトステネスの篩は、範囲内の素数をまとめて列挙するための代表的なアルゴリズムです。候補をTrueで初期化し、見つかった素数の倍数をFalseへ変えていきます。

その発想では、2の倍数、3の倍数、5の倍数というように、合成数を篩い落とします。すでに小さい素数の倍数として消えている候補は再処理を避けられるため、範囲列挙で力を発揮すると言えるでしょう。

from math import isqrt

def sieve_of_eratosthenes(limit):
    if limit < 2:
        return []
    is_prime = [True] * (limit + 1)
    is_prime[0] = False
    is_prime[1] = False

    for p in range(2, isqrt(limit) + 1):
        if is_prime[p]:
            for multiple in range(p * p, limit + 1, p):
                is_prime[multiple] = False

    return [number for number, flag in enumerate(is_prime) if flag]

print(sieve_of_eratosthenes(30))

結果: 期待される出力は、[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]です。

これでp * pから倍数を消しているのは、それより小さいpの倍数が小さい素数によって処理済みになるためです。例えば5 * 2や5 * 3は、2や3の段階で合成数として扱われています。

ただし、篩はlimit + 1個の真偽値を持つリストを使います。上限が非常に大きい場合はメモリ消費が増えるため、単一判定と範囲列挙を目的に応じて分ける必要があるのが基本です。

公式ドキュメントによれば、enumerate()は反復可能オブジェクトからインデックスと値を同時に取り出せますが、これは押さえたい点です。篩の最後でnumberとflagを同時に読む書き方は、この性質を利用しています。

素数判定の早見表

Pythonでの素数判定の応用例

Pythonで素数判定を応用する場面では、単にTrueかFalseを返すだけでなく、範囲内の素数を集めたり、特定の数学的性質を持つ数を探したりします。プログラミング学習としては、関数の合成やリスト処理の練習にもなります。

これをアプリや自動処理に広げる場合、範囲列挙、条件検索、結果の整形がよく使われますが、覚えておくと役立つでしょう。Python全般の入口を確認したい場合は、Python初心者のための完全ガイド！アプリ化の10ステップも関連すると覚えるとよいでしょう。

範囲内の素数を列挙する

範囲内の素数を列挙するなら、終点までの素数リストを作り、開始値以上だけを残す設計が分かりやすいです。その場合、篩で得た結果をlistとして受け取り、内包表記で絞り込みます。

def primes_in_range(start, end):
    primes = sieve_of_eratosthenes(end)
    return [p for p in primes if p >= start]

print(primes_in_range(1, 30))
print(primes_in_range(50, 80))

結果: 期待される出力は、[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]と[53, 59, 61, 67, 71, 73, 79]です。

この関数はstartとendを受け取り、閉区間に近い感覚で素数を返します。厳密には終点endを含むため、Pythonの一般的な半開区間とは少し違う設計です。

そのため、関数名やドキュメント文字列で終点を含むことを明示すると誤用を防げます。コーディングでは、処理そのものだけでなく、呼び出す側が迷わない形に整えることも大切になるのが目安です。

特定の条件の素数を探索する

双子素数は、差が2である素数のペアを指すると考えられます。例えば3と5、5と7、11と13は、どちらも素数で差が2なので双子素数として扱えます。

一方、メルセンヌ素数は2**p - 1の形で表される素数です。pが素数でも常に2**p - 1が素数になるわけではないため、ここでも素数判定が必要になるのがポイントです。

def twin_prime_pairs(limit):
    return [(p, p + 2) for p in range(2, limit - 1)
            if is_prime_fast(p) and is_prime_fast(p + 2)]

def mersenne_primes(max_p):
    results = []
    for p in range(2, max_p + 1):
        candidate = 2**p - 1
        if is_prime_fast(p) and is_prime_fast(candidate):
            results.append(candidate)
    return results

print(twin_prime_pairs(30))
print(mersenne_primes(19))

結果: 期待される出力は、双子素数のペアとして[(3, 5), (5, 7), (11, 13), (17, 19)]など、メルセンヌ素数として[3, 7, 31, 127, 8191, 131071, 524287]です。

これでtwin_prime_pairs()はペアを重複なく返します。元記事のように片側の素数だけを表示する方法もありますが、ペアの形にすると差が2であることを視覚的に確認しやすくなります。

ただし、2**p - 1は指数の増加により急速に大きくなるのが一般的です。大きな候補を扱う場合、試し割りの素数判定では時間がかかるため、用途に応じて専門的な手法を検討すると言えるでしょう。

その応用先として、表データに素数フラグを付ける処理や、グラフ化して分布を見る学習も考えられます。データの整形には初心者必見！Pythonで表を操作するための7つの詳細ガイド、可視化にはPythonで折れ線グラフ作成の完全ガイド10選が関連するのが現実的です。

よくあるエラーと対処法

素数判定のコーディングで初心者がつまずきやすいのは、剰余演算、範囲の終端、平方根の扱い、入力値の型です。エラーが出ないコードでも、数学的に間違った結果を返す場合があります。

これらは文法エラーより発見しづらいため、1、2、4、9、49のような境界値をテストに含めると効果的です。特に平方数は、平方根の終端ミスを見つけやすい入力になるのが基本です。

割り算と剰余演算の混同

よくある誤りは、n / i == 0で割り切れるかを判定しようとする書き方です。/は割り算の商を返す演算子なので、正の整数どうしでは0になりません。

def wrong_is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n / i == 0:
            return False
    return True

print(wrong_is_prime(4))

結果: 期待される出力はTrueですが、4は素数ではないため、判定ロジックとして誤りです。

その修正では、余りを返す%を使います。4 % 2は0になるため、4が2で割り切れることを条件式で表せます。

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

print(corrected_is_prime(4))

結果: 期待される出力はFalseです。

平方根の終端ミス

平方根まで調べる実装では、range(2, isqrt(n))のように終端を含め忘れるミスがあります。range()は第二引数の値を含まないため、平方数の判定で誤りが出ます。

from math import isqrt

def missing_endpoint(n):
    if n <= 1:
        return False
    for i in range(2, isqrt(n)):
        if n % i == 0:
            return False
    return True

print(missing_endpoint(49))

結果: 期待される出力はTrueですが、49は7で割り切れるため、この関数は誤った判定になると整理できるのが目安です。

この修正は、終端をisqrt(n) + 1にするだけです。境界値のテストに9、25、49を入れると、同じ種類の誤りを拾いやすくなります。

from math import isqrt

def include_endpoint(n):
    if n <= 1:
        return False
    for i in range(2, isqrt(n) + 1):
        if n % i == 0:
            return False
    return True

print(include_endpoint(49))

結果: 期待される出力はFalseです。

浮動小数点数を経由する問題

大きな整数の平方根をn**0.5で求めると、floatを経由します。Pythonのintは任意精度整数として扱われますが、floatには表現精度の限界があります。

そのため、整数のまま平方根の床を得たい場合はmath.isqrt()を使いると理解できるのがポイントです。公式ドキュメントでもmath.isqrt()は非負整数の整数平方根を返す関数として示されています。

from math import isqrt

def safe_is_prime(n):
    if not isinstance(n, int):
        raise TypeError("n must be an integer")
    if n <= 1:
        return False
    for i in range(2, isqrt(n) + 1):
        if n % i == 0:
            return False
    return True

print(safe_is_prime(97))

結果: 期待される出力はTrueです。

これでisinstance(n, int)を入れているのは、入力値の型を明確にするためです。文字列や小数を受け入れる設計にする場合は、関数の外側でint()変換や例外処理を分けると整理しやすくなります。

入力欄から値を受け取るアプリでは、改行や空文字が混ざることもあります。文字列処理を学ぶなら、Pythonで改行あり・なしを制御する方法と応用例10選の内容も関連すると覚えるとよいでしょう。

素数判定コードの最適化と詳細解説

素数判定コードの最適化では、処理時間だけでなく、正確性、読みやすさ、入力の扱いを同時に見ますし、これが一つの目安です。速くても境界値で誤る関数は使いにくく、正しくても意図が読めない関数は保守しづらくなります。

基本的に、単一判定ではis_prime_fast()、範囲列挙ではsieve_of_eratosthenes()を選ぶと整理しやすいです。複数の処理を同じ関数に詰め込むより、目的ごとに関数を分けるほうがテストもしやすくなると考えられます。

パフォーマンス比較と最適化の観点

速度を比較する場合は、同じ入力、同じ回数、同じ環境で測る必要があるのが一般的です。Python標準ライブラリのtimeitは、小さなコード片の実行時間を測るためのモジュールです。

from math import isqrt
from timeit import timeit

def is_prime_fast(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, isqrt(n) + 1, 2):
        if n % i == 0:
            return False
    return True

elapsed = timeit("is_prime_fast(1000003)", globals=globals(), number=1000)
print(elapsed)

結果: 期待される出力は秒数を表す浮動小数点数です。値はCPU、Pythonのビルド、実行中の負荷によって変わります。

この例では、具体的な秒数を固定して扱いません。動作未確認の環境で数値を断定すると、読者の環境との差を誤解させるためです。

一方、比較の考え方は明確です。単純版は候補を広く調べ、平方根版は上限を絞り、偶数除外版は候補の半分を外します。

完成形として扱いやすい素数判定関数

実用寄りの関数としては、型注釈を付け、math.isqrt()を使い、偶数を早めに除外する形が扱いやすいです。戻り値がboolであることも明示できると言えるでしょう。

from math import isqrt

def is_prime(n: int) -> bool:
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    limit = isqrt(n)
    for divisor in range(3, limit + 1, 2):
        if n % divisor == 0:
            return False
    return True

assert is_prime(1) is False
assert is_prime(2) is True
assert is_prime(49) is False
assert is_prime(97) is True

結果: 期待される動作は、すべてのassertが通過し、出力なしで終了することです。

これでlimitという変数を置くと、ループ上限の意味が読み取りやすくなります。短い式を直接書くより、数学的な境界を名前で残すほうが後から変更しやすい場合があります。

ただし、型注釈は実行時に自動で型を検査する仕組みではありません。必要ならisinstance()で検査するか、呼び出し側で入力を整数に正規化するのが基本です。

範囲列挙を再利用しやすくする

範囲列挙の関数は、上限だけでなく、開始値と終了値を受け取る形にすると再利用しやすくなるのが現実的です。そのうえで、end < 2やstart > endのような入力も先に処理します。

def primes_between(start: int, end: int) -> list[int]:
    if start > end or end < 2:
        return []
    primes = sieve_of_eratosthenes(end)
    lower = max(start, 2)
    return [p for p in primes if p >= lower]

print(primes_between(10, 30))
print(primes_between(30, 10))

結果: 期待される出力は、[11, 13, 17, 19, 23, 29]と[]です。

この形なら、表データの加工、コマンドラインツール、Webフォームの入力処理に組み込みやすくなります。画面操作の自動化と組み合わせる文脈では、Pythonで実現！ウィンドウ操作の自動化15選のような周辺知識も役立ちます。

一般に、アルゴリズムの最適化は一度で終わる作業ではありません。入力規模、求める結果、メモリ制約を見て、素数判定の方法を選び直すのが自然です。

まとめ

Pythonの素数判定は、数学の定義をプログラミングの条件分岐へ変換する題材です。1以下を除外し、割り切れる候補を探し、平方根までで止める流れを押さえると、基本のアルゴリズムを理解できるのが目安です。

そのうえで、偶数を先に除外する書き方や、math.isqrt()を使う書き方に進むと、正確性と効率を両立しやすくなると整理できます。範囲内の素数をまとめて扱うなら、エラトステネスの篩が有力な選択肢です。

一方、コーディングでは/と%の混同、range()の終端、floatへの変換が誤りの原因になりやすいです。境界値を含むassertを置くと、関数の意図を保ちやすくなります。

これらを整理すると、単一判定、範囲列挙、条件付き探索を切り分けて関数化する設計が扱いやすいと言えますし、ここを基本と考えるとよいでしょう。素数判定は小さなテーマですが、アルゴリズム、数学、プログラミングの接点を学ぶ練習として使いやすい題材です。

関連記事

• Python初心者のための完全ガイド！アプリ化の10ステップ
• Pythonで実現！ウィンドウ操作の自動化15選
• Pythonで折れ線グラフ作成の完全ガイド10選
• 初心者必見！Pythonで表を操作するための7つの詳細ガイド
• Pythonで改行あり・なしを制御する方法と応用例10選

※本記事は実在のエンジニア複数名で構成される Japanシーモア編集部が、AI支援を活用して作成・校正・公開しています。