ユークリッドの互除法
出典: 平成29年度 春期 応用情報技術者試験 午前 問6 (IPA)
次の流れ図の処理で，終了時の x に格納されているものはどれか。ここで，与えられた a，b は正の整数であり，mod(x，y) は x を y で割った余りを返す。
- ア a と b の最小公倍数
- イ a と b の最大公約数
- ウ a と b の小さい方に最も近い素数
- エ a を b で割った商
正解と解説を見る
正解: イ
- ア: 最小公倍数は、最大公約数を求めた後に a × b ÷ 最大公約数 で求めます。この流れ図では求めていません。
- イ: 余りを取りながら値を入れ替えるユークリッドの互除法なので、x は最大公約数になります。正しい答えです。
- ウ: 素数を調べる処理はありません。
- エ: 商ではなく余り (mod) を繰り返し求めています。
ポイント
- 流れ図は、x を y で割った余りを求め、(x, y) ← (y, 余り) とし、y が 0 になるまで 繰り返します。
- これは ユークリッドの互除法 で、終了時の x は 最大公約数 です。
- 例: a ＝ 24, b ＝ 18 → (18, 6) → (6, 0) となり、x ＝ 6