ユークリッドの互除法の可視化 — 最大公約数をフローチャートで
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とその数の最大公約数はその数自身）になります。
🧩 手を動かして深めるなら：この「割り算の余り」を使う考え方は、擬似言語のトレース練習にも直結します。擬似言語ステッパーで while ループの動きを、探索・ソートの可視化でフローチャート付きのアルゴリズムを、それぞれ確かめられます。
基本情報技術者試験ではこう出る
「ユークリッドの互除法で最大公約数を求める手順」「擬似言語で書かれた互除法をトレースする」「ループが何回で終わるか」などが出題されます。余り ← a mod b、a ← b、b ← 余り を b=0 まで繰り返すという流れを、上のフローチャートで体に入れておくと、科目Bのトレース問題でも迷いません。関連：擬似言語ステッパー ／ 探索アルゴリズム ／ 可視化一覧。