Pythonで学ぶエラトステネスの篩（ふるい）：素数を効率的に求めるアルゴリズム

本記事では、以下の問題文に対する解決策について、Pythonでの実装方法をわかりやすく解説します。

問題の概要

問題文： 整数 n が与えられたとき、n 以下のすべての素数を出力してください。
制約： n は小さな数とします。

素数を列挙する古典的な手法として知られる「エラトステネスの篩（Sieve of Eratosthenes）」は、指定した範囲内の素数を効率よく見つけるためのアルゴリズムです。それでは、実際の実装を見ていきましょう。

サンプルコード

def SieveOfEratosthenes(n):
    # Trueで初期化されたboolean型の配列を作成
    prime = [True for i in range(n + 1)]
    p = 2
    while (p * p <= n):
        # 値が変更されていない場合、その数は素数
        if (prime[p] == True):
            # 素数pの倍数をすべて合成数としてマーク
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    # 0と1は素数ではないため除外
    prime[0] = False
    prime[1] = False
    # 結果の出力
    for p in range(n + 1):
        if prime[p]:
            print(p, end=" ")

# メイン処理
if __name__ == '__main__':
    n = 33
    print("33以下の素数は次の通りです")
    SieveOfEratosthenes(n)

実行結果

33以下の素数は次の通りです
2 3 5 7 11 13 17 19 23 29 31

アルゴリズムの仕組み

このプログラムでは、まず n + 1 個の要素を持つboolean型の配列を作成し、すべての値を True（素数候補）で初期化します。その後、2から順に各素数について、その倍数をすべて False（合成数）としてマークしていきます。ループ条件が p * p <= n となっているのは、n の平方根まで確認すれば十分だからです。これにより計算量を大幅に削減できます。

すべての変数はローカルスコープ内で宣言されており、処理の流れの中でそれぞれの参照関係を確認できます。最後に残った True の要素、すなわち素数のみを出力することで、n 以下のすべての素数が得られます。

まとめ

本記事では、エラトステネスの篩を用いて、n 以下の素数をすべて求めるPythonプログラムの実装方法を学びました。このアルゴリズムは時間計算量 O(n log log n) で動作し、小〜中規模の範囲における素数列挙において非常に効率的な手法です。競技プログラミングや数学的な問題を解く際にも頻繁に活用されるので、ぜひ理解しておきましょう。