エラトステネスの篩の可視化 — 素数をフローチャートで
素数（1と自分自身でしか割り切れない数）を効率よく見つける古典的アルゴリズムです。やり方はシンプルで、小さい数から順に、その数の倍数を消していくだけ。最後まで消されずに残った数が素数です。下のグリッドとフローチャートを1ステップずつ進めて、数がふるい落とされていく様子を見てください。
🔀 フローチャート（いま実行中の処理が光ります）
いま何をしているか
エラトステネスの篩とは
2からNまでの数を並べ、小さい素数から順に、その倍数を消していく方法です。「篩（ふるい）」の名のとおり、合成数（素数でない数）をふるい落とし、残った数が素数になります。手順はこうです。
手順1： まだ消えていない一番小さい数 p（最初は2）は素数。
手順2： p の倍数（2p, 3p, …）をすべて消す。
手順3： 次に残っている数へ進み、繰り返す。p×p が N を超えたら終了（それ以上は新たに消える数がない）。
なぜ「p×p まで」で十分なのか
N以下の合成数は、必ず√N 以下の素因数を持ちます。だから p が √N（＝ p×p が N）を超えたら、まだ消えていない数はすべて素数と確定します。無駄な走査を省ける、賢い打ち切り条件です。
つまずきやすいポイント
1は素数ではない。 篩を2から始めるのはこのためです。素数は「1とその数自身のちょうど2つの約数を持つ数」と定義され、1は約数が1つ（自分だけ）なので素数に含めません。「1を素数と数えてしまう」のはよくある間違いです。
倍数を消すのは 2p ではなく p×p から始めてよい。 p の倍数のうち p×p より小さいもの（2p, 3p, …）は、それより小さい素数の段階ですでに消されています。だから消し始める位置を p×p にすると、重複した消し込みを省けて速くなります。
🧩 アルゴリズムをもっと動かすなら：ループと配列の操作は 擬似言語ステッパー、フローチャート付きの探索・並べ替えは 探索・ソート、最大公約数は ユークリッドの互除法 で確かめられます。
素数はどれくらいあるのか
| 範囲 | 素数の個数 |
|---|---|
| 30以下 | 10個 |
| 50以下 | 15個 |
| 100以下 | 25個 |
| 1,000以下 | 168個 |
| 10,000以下 | 1,229個 |
数が大きくなるほど、素数は少しずつまばらになっていきます。この可視化の「30まで」なら10個、「50まで」なら15個が最後に残ります。
1つずつ割って調べる方法との違い
ある数が素数かどうかを1つだけ調べるなら、2から√Nまでの数で割り切れるかを試す方法（試し割り）で十分です。しかし、N以下の素数をまとめて全部求めたいときは、篩のほうが速くなります。篩は「割り算」をせず、倍数に印を付けていくだけだからです。計算量は O(N log log N) で、ほぼ N に比例して増える程度に収まります。そのかわり、N個分の印を記録する配列（メモリ）が必要です。
基本情報技術者試験ではこう出る
「エラトステネスの篩で素数を求める手順」「なぜ p×p（√N）まで調べれば十分か」「擬似言語での二重ループのトレース」などが問われます。小さい素数の倍数を消す → 残った数が素数という考え方を、上のグリッドとフローチャートで体に入れておきましょう。関連：ユークリッドの互除法 ／ 擬似言語ステッパー ／ 可視化一覧。
よくある質問
Q. 暗号で使う大きな素数も、篩で探しているの？
A. いいえ。RSA暗号などで使う素数は数百桁もあり、そこまでの表は作れません。大きな素数は、確率的な判定法（ミラー・ラビン法など）で調べます。篩は、小さな素数の一覧をすばやく作る場面で使われます。