Pythonで素数を見つける3つの方法――全約数チェックからエラトステネスの篩まで徹底比較

素数とは、1とその数自身でしか割り切れない正の整数のことです。「ある数が素数かどうか」を判定する処理は、古くからプログラミングにおける定番の課題の一つとされてきました。しかも、判定アルゴリズムには複数のアプローチが存在し、それぞれ計算効率が大きく異なります。

本記事では、Pythonで素数を求める代表的な3つの方法を紹介し、実際の実行時間をもとに、どの手法が最も効率的なのかを検証します。

方法1: すべての約数を順番にチェックする

もっともシンプルなのがこの方法です。2から「対象の数 − 1」までのすべての整数で順番に割り算を行い、一度でも余りが0になれば素数ではないと判断します。最後まで割り切れる数が見つからなければ、その数は素数です。

サンプルコード

import time

# 素数かどうかを判定する関数
def check_prime(final_val):
    if final_val <= 1:
        return False
    for divisor in range(2, final_val):
        if final_val % divisor == 0:
            return False
    return True

# 開始時刻を記録
StartTime = time.time()

# 素数の個数をカウント
cnt = 0
for final_val in range(1, 10001):
    if check_prime(final_val):
        cnt += 1

print('10000までの素数の個数:', cnt)

# 終了時刻を記録
EndTime = time.time()
print('経過時間:', EndTime - StartTime)

実行結果

10000までの素数の個数: 1229
経過時間: 2.31秒前後

この方法はロジックが直感的で理解しやすい反面、毎回ほぼすべての数で割り算を繰り返すため、処理に時間がかかることがわかります。

方法2: 平方根(√N)までの約数だけをチェックする

数学的には、ある数 N が素数かどうかを判定するとき、√N 以下の数で割り切れるかを確かめるだけで十分です。なぜなら、もし N が a × b(a ≤ b)と分解できるなら、必ず a ≤ √N となるためです。

この性質を使うことでループ回数を大幅に減らせます。具体的な手順は次のとおりです。

• 判定したい数の平方根を求める。
• 2から平方根(切り捨て)までの各値で順番に割り算を行う。
• 途中で一度でも余りが0になったら、その数は素数ではないと判断して終了する。

サンプルコード

import math
import time

def is_prime(final_val):
    # 1 は素数ではない
    if final_val <= 1:
        return False
    i = 2
    while i <= math.floor(math.sqrt(final_val)):
        # 余りが0になるかどうかを確認
        if final_val % i == 0:
            return False
        i += 1
    return True

# 開始時刻を記録
StartTime = time.time()
cnt = 0
for n in range(1, 10001):
    if is_prime(n):
        cnt += 1

print('10000までの素数の個数:', cnt)

# 終了時刻を記録
EndTime = time.time()
print('経過時間:', EndTime - StartTime)

実行結果

10000までの素数の個数: 1229
経過時間: 0.053秒前後

同じ範囲(1〜10000)を判定したにもかかわらず、方法1と比べて実行時間が大幅に短縮されました。ループの上限を √N に抑えるだけで、これほど大きな差が生まれます。

方法3: エラトステネスの篩(ふるい)

3つ目は古典的かつ非常に有名なアルゴリズム「エラトステネスの篩」です。これは素数を一つずつ「見つける」のではなく、素数以外の数(合成数)を順番に「ふるい落としていく」ことで、指定した数までの素数をすべて抽出します。

手順は以下のとおりです。

• 2から素数を求めたい上限の数までの連続した整数リストを作成する。
• 先頭の数(まずは2)を残し、その倍数をすべてリストから除外する。続いて次の数(3)について同様の操作を繰り返す。ポイントは除外するのはあくまで「倍数」だけで、数自身は削除しないことです。たとえば5や11は決して消えませんが、10や22は除外されます。
• すべてのふるい落としが終わった後に残った数のリストが、求める範囲の素数一覧となります。

サンプルコード

import time

def sieve_method(n):
    # ふるい落とした数(合成数)を記録するリスト
    composite_numbers = []
    for i in range(2, n + 1):
        # 合成数リストに含まれていなければ素数として出力
        if i not in composite_numbers:
            print(i)
        # 自身の倍数(i*i 以降)を合成数リストへ追加
        for j in range(i * i, n + 1, i):
            composite_numbers.append(j)

# 開始時刻を記録
StartTime = time.time()
sieve_method(25)
# 終了時刻を記録
EndTime = time.time()
print('経過時間:', EndTime - StartTime)

実行結果

2
3
5
7
11
13
17
19
23
経過時間: 0.0秒前後

25までの素数が一瞬で列挙できました。エラトステネスの篩は、割り算を一切使わずに素数を抽出できる点が大きな特徴です。

まとめ: 実行時間から見る効率の違い

3つの方法の特徴を整理すると次のようになります。

単一の数の素数判定であれば「√N までの試し割り」がシンプルかつ十分に高速でおすすめです。一方、「ある範囲内のすべての素数を求めたい」場合には、大量の数を一括処理できるエラトステネスの篩が最適です。用途に応じてアルゴリズムを選択することが、効率的なプログラミングへの第一歩といえるでしょう。