エラトステネスの篩 ビジュアライザー
エラトステネスの篩(ふるい)アルゴリズムを数字グリッド上でアニメーション表示するツール。素数にマークを付け、合成数を消していく様子をステップごとに確認できます。すべてブラウザ内で動作します。
疑似コード
Run an operation to see its steps.
Avg · Worst
使い方
- 1 上限値n(最大150)を入力し、「Run sieve」を押します。
- 2 素数が一つずつマークされ、続いてその倍数がすべて合成数として消されていく様子を確認します。
- 3 ステップを前後に戻したり進めたりできるほか、「Random」で別の上限値を試すこともできます。
- 4 緑色のマスは素数、灰色のマスは合成数を表します。
このツールを使う理由
- 各素数pについて、なぜp²からマークを開始すればよいのかが直感的に理解できます。
- 合成数が次第に消えていき、最終的に素数だけがハイライトされて残る様子を目で見て確認できます。
- ほぼ線形に近いO(n log log n)という時間計算量の意味を体感できます。
- すべてブラウザ内で完結します。登録もアップロードも不要です。
よくある質問
エラトステネスの篩とは何ですか?
上限値nまでのすべての素数を見つけるための古典的なアルゴリズムです。まだマークされていない次の数(それが素数です)を順に取り出し、その倍数をすべて合成数としてマークしていく処理を繰り返します。
この篩アルゴリズムの時間計算量はどれくらいですか?
時間計算量はO(n log log n)、空間計算量はO(n)です。一つひとつの数について個別に素数判定を行うよりもはるかに高速です。
なぜ2pではなくp²からマークを始めるのですか?
p²より小さいpの倍数(2p、3pなど)は、すでにより小さい素因数を持っており、その素因数を処理した時点で既にマーク済みだからです。p²から始めることで、無駄な重複処理を避けられます。
1は素数ですか?
いいえ、違います。1は約数を1つしか持たないため、定義上は素数でも合成数でもありません。この篩アルゴリズムでも1は非素数として扱われます。
エラトステネスの篩 ビジュアライザー とは？
エラトステネスの篩 ビジュアライザーは、素数を求めるこの古典的なアルゴリズムの動きをアニメーションで見せるツールです。2から始めて、まだマークされていない数を素数として印を付け、その数のすべての倍数を合成数として消していきます。この作業を繰り返すことで、最終的にnまでの素数だけが残ります。
機能
ステップごとのアニメーション
2, 3, 5, … の倍数が次々と消されていき、素数だけが残る様子を確認できます。
計算量
時間計算量: O(n log log n)。空間計算量: 篩用の真偽値配列にO(n)。
100%プライベート
すべてブラウザ内で完結して実行され、データはどこにもアップロードされません。
例
Input
primes up to 30Output
2, 3, 5, 7, 11, 13, 17, 19, 23, 29主な用途
-
1
素数を高速に列挙する
指定した上限以下のすべての素数を効率的に生成します。
-
2
問題のための事前計算
数論や競技プログラミングの問題向けに素数テーブルを構築します。
-
3
篩のアイデアを学ぶ
倍数をマークする方法が、数値ごとの素数判定よりも優れている理由を理解できます。
Zerethonのエラトステネスの篩ビジュアライザーは、ブラウザ上で限界値nまでのすべての素数を見つける過程をアニメーションで表示し、各素数の倍数を合成数としてマークしていきます。この篩はO(n log log n)の時間計算量とO(n)の空間計算量で動作し、各数値を個別に素数判定するよりもはるかに高速です。
- カテゴリ
- アルゴリズム
- 料金
- 無料
- プライバシー
- ブラウザベース
- 登録
- 不要
参考文献
- Sieve of Eratosthenes — Wolfram MathWorld — Wolfram MathWorld
- Sieve of Eratosthenes — Wikipedia
プライバシー
明記されない限り、データがブラウザの外に送信されることはありません。エラトステネスの篩 ビジュアライザー は完全にクライアント側で動作します — サーバーへのアップロードなし、ログなし、入力内容のトラッキングなし。
初めての方へ。Big-O 解析付きのステップバイステップ解説を読む: Number Theory を学ぶ →
関連ツール
バブルソート ビジュアライザー
バブルソートの動きをアニメーションで確認できるツール。ステップ実行や速度調整、カスタム入力データ、比較・交換回数のリアルタイム表示、擬似コードの表示に対応しています。すべてブラウザ内だけで動作します。
ツールを開く挿入ソート(Insertion Sort)ビジュアライザー
挿入ソートをアニメーションで可視化。ステップ実行や速度調整、カスタム入力、比較回数・書き込み回数のリアルタイム表示、疑似コード(pseudocode)表示に対応。すべてブラウザ内で完結します。
ツールを開く選択ソート(Selection Sort)ビジュアライザー
ステップ実行、速度調整、カスタム入力、比較/交換回数のライブカウンター、擬似コードを備えたSelection Sortのアニメーション。すべてブラウザ内だけで完結します。
ツールを開くマージソート ビジュアライザー
マージソートの動きをアニメーションで再現するツールです。ステップ実行、速度調整、独自のデータ入力、比較・書き込み回数のリアルタイム表示、擬似コード表示に対応。すべてブラウザ上だけで動作します。
ツールを開くZerethon Social で作成・共有・成長しよう
無料登録。ポイントを獲得し、実績を集め、世界中のクリエイターとつながりましょう。