ユークリッドの互除法ビジュアライザー(GCD)
ユークリッドの互除法をアニメーションで表示 — (a, b) → (b, a mod b) という置き換えを繰り返しながら、2つの数の最大公約数(GCD)をステップごとに計算します。ブラウザ上でそのまま動作します。
疑似コード
Run an operation to see its steps.
Avg · Worst
使い方
- 1 カンマ区切りで2つの数値を入力し(例: 48, 36)、「GCDを計算」をクリックします。
- 2 b が 0 になるまで、(a, b) が (b, a mod b) に置き換わっていく様子をステップごとに確認します。
- 3 b が 0 になった時点で、a の値が最大公約数です。
- 4 「ランダム」で新しい数値ペアを生成するか、1回ずつ除算を進めることもできます。
このツールを使う理由
- 数学史上最も古いアルゴリズムの一つであるユークリッドの互除法が実際に動く様子を確認できます。
- なぜ gcd(a, b) = gcd(b, a mod b) が成り立つのか、そしてなぜこのアルゴリズムがこれほど速く終了するのかを理解できます。
- 値がどちらかが0になるまで対数的なペースで小さくなっていく様子を観察できます。
- すべてブラウザ内で完結します。登録不要、データのアップロードも不要です。
よくある質問
ユークリッドの互除法とは何ですか?
2つの整数の最大公約数(GCD)を求める方法で、大きい方の数を、それを小さい方の数で割った余りに置き換える操作を、余りが0になるまで繰り返します。
ユークリッドの互除法の時間計算量はどれくらいですか?
O(log min(a, b)) です。ステップ数は桁数に比例するため、非常に大きな数であっても極めて高速に計算できます。
なぜ gcd(a, b) = gcd(b, a mod b) が成り立つのですか?
a と b の公約数はすべて a mod b も割り切れます(その逆も同様です)。そのため、この置き換えを行っても公約数の集合、つまり最大公約数は変わりません。
GCDは何に使われますか?
分数の約分、モジュラー算術、拡張ユークリッドの互除法(モジュラー逆数、RSA)、そして lcm(a,b) = a·b / gcd(a,b) の式による最小公倍数の計算などに使われます。
ユークリッドの互除法ビジュアライザー(GCD) とは？
ユークリッドの互除法ビジュアライザーは、整数のペア (a, b) を (b, a mod b) に繰り返し置き換えていき、b が 0 になった時点の a が最大公約数になる、という2つの整数のGCDを求める仕組みをシミュレートするツールです。
ユークリッドの互除法ビジュアライザー(GCD) は Zerethon Tools が提供する無料の アルゴリズム ユーティリティです。ユークリッドの互除法をアニメーションで表示 — (a, b) → (b, a mod b) という置き換えを繰り返しながら、2つの数の最大公約数(GCD)をステップごとに計算します。ブラウザ上でそのまま動作します。. ブラウザ上で完全に動作します — 登録不要、アップロード不要。
- カテゴリ
- アルゴリズム
- 料金
- 無料
- プライバシー
- ブラウザベース
- 登録
- 不要
プライバシー
明記されない限り、データがブラウザの外に送信されることはありません。ユークリッドの互除法ビジュアライザー(GCD) は完全にクライアント側で動作します — サーバーへのアップロードなし、ログなし、入力内容のトラッキングなし。
初めての方へ。Big-O 解析付きのステップバイステップ解説を読む: Number Theory を学ぶ →
比較
関連ツール
バブルソート ビジュアライザー
バブルソートの動きをアニメーションで確認できるツール。ステップ実行や速度調整、カスタム入力データ、比較・交換回数のリアルタイム表示、擬似コードの表示に対応しています。すべてブラウザ内だけで動作します。
ツールを開く挿入ソート(Insertion Sort)ビジュアライザー
挿入ソートをアニメーションで可視化。ステップ実行や速度調整、カスタム入力、比較回数・書き込み回数のリアルタイム表示、疑似コード(pseudocode)表示に対応。すべてブラウザ内で完結します。
ツールを開く選択ソート(Selection Sort)ビジュアライザー
ステップ実行、速度調整、カスタム入力、比較/交換回数のライブカウンター、擬似コードを備えたSelection Sortのアニメーション。すべてブラウザ内だけで完結します。
ツールを開くマージソート ビジュアライザー
マージソートの動きをアニメーションで再現するツールです。ステップ実行、速度調整、独自のデータ入力、比較・書き込み回数のリアルタイム表示、擬似コード表示に対応。すべてブラウザ上だけで動作します。
ツールを開くZerethon Social で作成・共有・成長しよう
無料登録。ポイントを獲得し、実績を集め、世界中のクリエイターとつながりましょう。