応用情報技術者試験 応用情報技術者試験 平成29年度春期 午前 問6: 次の流れ図の処理で，終了時の x に格納されているものはどれか。ここで，与えられた a，b は正の整数であり，mod(x,y) は x を y で割った余りを返

正解

イ. a と b の最大公約数

正答率 57.3%（777人中 445人が正解）

問題の解説

流れ図はユークリッドの互除法である。x を y で割った余りを t とし、x←y、y←t と更新することを、y が 0 になるまで繰り返すと、そのときの x が a と b の最大公約数になる。例えば a=12、b=18 では (x, y) が (12, 18)→(18, 12)→(12, 6)→(6, 0) と変わり、x=6 が結果になる。

選択肢ごとの解説

• ア最小公倍数は a×b を最大公約数で割って求める値で、この流れ図が求める値ではない。a=12、b=18 の最小公倍数は 36 だが、結果は 6 になる。
• イ正しい。余りで割る数を置き換えながら割り続ける互除法で、y が 0 になったときの x が、a と b の最大公約数になる。
• ウ素数を探す処理ではない。a=12、b=18 では結果が 6 になり、6 は素数ですらない。
• エ商は求めておらず、使っているのは割り算の余りだけである。結果の x も商ではなく、最大公約数になる。