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

問題本文

次の流れ図の処理で，終了時の x に格納されているものはどれか。ここで，与えられた a，b は正の整数であり，mod(x,y) は x を y で割った余りを返す。

選択肢

• ア.a と b の最小公倍数
• イ.a と b の最大公約数
• ウ.a と b の小さい方に最も近い素数
• エ.a を b で割った商

正解

イ. a と b の最大公約数

解説

この流れ図は剰余（mod）を使ったユークリッドの互除法そのもので、最大公約数（GCD）を求めるアルゴリズムである。x←a、y←b から始め、yが0になるまで「t←mod(x,y)（余り）、x←y、y←t」を繰り返すと、最後にxに最大公約数が残る。よって正解はイ。具体例ではa=12,b=8のとき、mod(12,8)=4→(x,y)=(8,4)、mod(8,4)=0→(x,y)=(4,0)で終了し、x=4＝gcd(12,8)となる。

選択肢ごとの解説

• ア.最小公倍数はこの手順では求まらない。互除法は剰余を用いて公約数を縮約していく処理で、結果は最大公約数である。誤り。
• イ.正しい。yが0になった時点でxに残る値が最大公約数。これは剰余を使ったユークリッドの互除法の定義どおりの動作である。
• ウ.素数を探す処理（割り切れるかの試し割りなど）は含まれておらず、素数とは無関係。誤り。
• エ.商を求めるなら除算や減算回数の計数が必要だが、この流れ図は余りを次の割られる数に渡す互除法であり商は得られない。誤り。