アルゴリズムとデータ構造

エラトステネスの篩 (Sieve of Eratosthenes)

n 未満の素数を探す際、2 から n までの各数について素数かどうかを個別に判定するよりも、はるかに高速な方法があります。これは、1 つひとつの数を判定するのではなく、「素数にならないことがわかっている数」をあらかじめ積極的にリストから除いていくアプローチです。
Video preview
最初に、2 から n までの全ての数を「素数かもしれない」という状態にしておきます。次に、まず 2 の倍数を全てリストから除外し、2 を「確実に素数」としてマークします。その後、3 の倍数を全て除外し、3 を「確実に素数」とします。4 は 2 の倍数の処理で既に除外されているためスキップします。次に扱うのは 5 なので、5 の倍数を全て除外します。6 は 2 の倍数のときに除外済みなのでスキップします。このように、n に達するまで同様の手順を繰り返します。
エラトステネスの篩のシミュレーション。 数をクリックして、素数を有効にし、それ以外の数を無効にしてみましょう。

アルゴリズムの面白い特徴と最適化

最小の素数 (2) から始めて、順番に素数 p の倍数をリストから除いていくと、p の倍数を 2·p, 3·p, 4·p, 5·p... とすべて調べる代わりに、最初から p·p を対象にできるようになります。なぜなら、2·p, 3·p, 4·p といった小さい倍数は、既に 2 や 3、5 などを処理した段階で除外されているからです。その結果、一番最初に未処理のまま残っている倍数は p·p となります。
たとえば、p=3 のときは 9 (3×3) からスタートできます。6 は 2 の段階で除外されているからです。p=5 のときも同様に 25 (5×5) から始めます。10 (2·5) は 2 で除外され、15 (3·5) は 3 で除外され、20 (4·5) は 2 で除外されているためです。
prime = [True] * n                    # prime[i] = True => i は素数を表す
prime[0] = prime[1] = False           # 0 と 1 は素数ではない

for i in range(2, n):                 # 2 から n までループ
    if prime[i]:                      # i が素数であれば
        for j in range(i * i, n, i):  # i より小さい倍数はすでにマーク済みなので、ループは i * i から開始
            prime[j] = False
Sieve of Eratosthenes to find all the prime numbers smaller than n.
n=100 の場合で手順を追ってみましょう:
prime = [False, False, True, True, ..., True] (サイズ 100)
  1. i = 2 ⇒ prime[2] = True ⇒ for j in 4, 6, 8, ... 100 で prime[j] = False にマーク
  1. i = 3 ⇒ prime[3] = True ⇒ for j in 9, 12, ... 100 で prime[j] = False にマーク
  1. i = 4 ⇒ prime[4] = False
  1. i = 5 ⇒ prime[5] = True ⇒ for j in 25, 30, ... 100 で prime[j] = False にマーク
  1. i = 6 ⇒ prime[6] = False
  1. i = 7 ⇒ prime[7] = True ⇒ for j in 49, 56, ... 100 で prime[j] = False にマーク
  1. i = 8 ⇒ prime[8] = False
  1. i = 9 ⇒ prime[9] = False
  1. i = 10 ⇒ prime[10] = False
  1. i = 11 ⇒ prime[11] = True ⇒ for j in [empty] で prime[j] = False にマーク
  1. この段階で i * i はすでに n を超えるので、これ以降はループ内で prime[j] = False をマークすることはありません。よって、この最後の段階で 100 未満の素数をリストから取得すれば完了します。
この手法は、実行にかかる処理回数が となり、とても高速です。これは大きな改善で、 に比べても非常に効率的です。たとえば、n 回の操作をすると 10 年（約 3650 日）かかるアルゴリズムが、 回で 2 ヶ月（約 61 日）に短縮できる場合でも、なんと 回の操作なら 4 日以内に終わるほどの差があります。
また、シミュレーションでも触れられていますが、i を 2 から までループさせる最適化もあります。内側のループは i·i が始点で、そこが n を超えると prime[j] = False をマークする必要がなくなるためです。

入力

入力の最初の行には整数 n (2 ≤ n ≤ ) が 1 つ与えられます。

出力

プログラムは n 以下の素数をすべて出力する必要があります。

例

入力
出力
8
2 3 5 7
17
2 3 5 7 11 13 17
19
2 3 5 7 11 13 17 19
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue