平成29年度春期 応用情報技術者試験 午前 問6

正解：イ

AI解説

正解はイ。この流れ図は、xとyの大きい方から小さい方の剰余を取る操作（mod）を、余りが0になるまで繰り返すユークリッドの互除法である。互除法は「aとbの最大公約数は、aをbで割った余りrとbの最大公約数に等しい」という性質を利用したアルゴリズムで、終了時のxには最大公約数（GCD）が格納される。 ア: 最小公倍数（LCM）を直接求めるアルゴリズムではない。なお最小公倍数は a×b÷最大公約数 で求められる。 イ: 正しい。剰余を取りながら値を入れ替えるユークリッドの互除法であり、終了時のxは最大公約数である。 ウ: 素数を求める処理（素数判定やエラトステネスのふるい）は含まれておらず、誤りである。 エ: 商を求めるだけなら繰返しは不要であり、mod演算を繰り返す本アルゴリズムの動作と一致しない。 💡 「mod（剰余）を余りが0になるまで繰り返す」流れ図・擬似コードを見たら即ユークリッドの互除法=最大公約数と判断してよい。具体値（例：a=12,b=8→4）でトレースして確認する習慣も有効。