エラトステネスの篩 | アルゴリズムビジュアル大事典

シンボル

データ
P[i]が1のときiが素数である素数表P

初期化
2以上の数を素数の候補として初期化します。
2の倍数を削除
2の倍数を合成数とします。P[j] ← 0
奇数の素数の倍数を削除
素数として残します。i
残した数の倍数を合成数とします。P[j] ← 0
素数表を確定します。区間[0, i*i]
素数リストを出力
素数を列挙します。

アニメーション

初期化
エラトステネスの篩 | 初期化

2の倍数を削除
エラトステネスの篩 | 2の倍数を削除

奇数の素数の倍数を削除
エラトステネスの篩 | 奇数の素数の倍数を削除

素数リストを出力
エラトステネスの篩 | 素数リストを出力