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

この流れ図は，yが0になるまで「xをyで割った余りを求め，xにyを，yに余りを入れる」ことを繰り返すもので，ユークリッドの互除法です。

例：a＝12，b＝8 の場合 - t＝mod(12,8)＝4，x＝8，y＝4 - t＝mod(8,4)＝0，x＝4，y＝0 → 終了

終了時の x＝4 は，12と8の最大公約数です。

• ア: aとbの最小公倍数
  誤り。例の12と8の最小公倍数は24ですが，終了時のxは4です。最小公倍数は，最大公約数を求めた後に a×b÷最大公約数 で求めます。

• イ: aとbの最大公約数
  正しい。ユークリッドの互除法により，終了時のxにはaとbの最大公約数が入ります。

• ウ: aとbの小さい方に最も近い素数
  誤り。例の12と8では8に最も近い素数は7ですが，終了時のxは4です。

• エ: aをbで割った商
  誤り。例の12÷8の商は1ですが，終了時のxは4です。

答え

イ: aとbの最大公約数