Pythonでn以下の素数リストを生成する方法【エラトステネスの篩】

問題概要

ある整数 n が与えられたとき、n 以下のすべての素数を昇順に並べたリストを生成することを考えます。なお、1 は素数ではない点に注意が必要です。

例えば、入力が 12 の場合、出力は [2, 3, 5, 7, 11] となります。

解決のアプローチ：エラトステネスの篩

この問題は、古典的なアルゴリズムである「エラトステネスの篩（ふるい）」を使うことで効率的に解けます。手順は以下のとおりです。

• サイズ n+1 のブール値リスト sieve を作成し、すべて True で初期化します。
• 結果を格納するための空のリスト primes を用意します。
• i を 2 から n まで順番に処理します。
  • sieve[i] が True の場合：
    • i を primes の末尾に追加します。
    • i の倍数にあたる要素をすべて False に設定し、合成数としてマークします。
• 最後に primes を返します。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, n):
        sieve = [True] * (n + 1)
        primes = []
        for i in range(2, n + 1):
            if sieve[i]:
                primes.append(i)
                for j in range(i, n + 1, i):
                    sieve[j] = False
        return primes

ob = Solution()
print(ob.solve(12))

入力

12

出力

[2, 3, 5, 7, 11]

計算量と最適化のポイント

エラトステネスの篩の時間計算量は O(n log log n)、空間計算量は O(n) です。各数値ごとに約数の有無を調べる単純な方法（O(n√n)）と比べて大幅に高速であり、大きな n に対しても実用的です。

さらに高速化したい場合は、内側のループを range(i * i, n + 1, i) から始めるのが定番の最適化です。i より小さい i の倍数は、すでにより小さい素数の処理時にマーク済みだからです。