ユークリッドの互除法の可視化 — 最大公約数をフローチャートで
2つの数の最大公約数（GCD）を求める、古くて強力なアルゴリズムです。やることはシンプルで、「大きい数を小さい数で割った余り」を求め、それを繰り返すだけ。余りが0になったときの割る数が答えです。右のフローチャートを1ステップずつ通過しながら、a と b がどう変わるかを見てください。
🔀 フローチャート（いま実行中の処理が光ります）
いま何をしているか
ユークリッドの互除法とは
2つの整数の最大公約数（GCD：Greatest Common Divisor）を効率よく求める方法です。素因数分解しなくても、「割った余りで割り続ける」だけで求まります。手順はこうです。
手順1： a を b で割った余り r を求める。
手順2： a に b を、b に r を入れる（割る数と余りにずらす）。
手順3： b が 0 になるまで繰り返す。b が 0 になったときの a が最大公約数。
なぜこれで最大公約数が求まるのか
ポイントは「a と b の最大公約数は、b と（a を b で割った余り）の最大公約数に等しい」という性質です。余りに置き換えても最大公約数は変わらないので、数をどんどん小さくしていけるのです。最後に片方が0になれば、もう片方がそのまま答え（0とその数の最大公約数はその数自身）になります。
つまずきやすいポイント
a と b の大小は気にしなくてよい。 もし a より b のほうが大きくても、最初の1回で自然に入れ替わります。たとえば a=462、b=1071 なら「462 を 1071 で割った余りは 462」なので、次のステップで a=1071、b=462 となり、以降は大きい数から処理が進みます。だから入力の順番を気にする必要はありません。
「引き算版」より「余り版」のほうが速い。 互除法には、大きい数から小さい数を引き続ける古い方式もあります。答えは同じですが、1071 − 462 − 462 … と何度も引くより、割り算の余り（mod）で一気に飛ばすほうが手数が少なく済みます。上の可視化は余り版です。
🧩 手を動かして深めるなら：この「割り算の余り」を使う考え方は、擬似言語のトレース練習にも直結します。擬似言語ステッパーで while ループの動きを、探索・ソートの可視化でフローチャート付きのアルゴリズムを、それぞれ確かめられます。
基本情報技術者試験ではこう出る
「ユークリッドの互除法で最大公約数を求める手順」「擬似言語で書かれた互除法をトレースする」「ループが何回で終わるか」などが出題されます。余り ← a mod b、a ← b、b ← 余り を b=0 まで繰り返すという流れを、上のフローチャートで体に入れておくと、科目Bのトレース問題でも迷いません。関連：擬似言語ステッパー ／ 探索アルゴリズム ／ 可視化一覧。