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

選択肢

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

正解と解説

正解：イ aとbの最大公約数

xをyで割った余りをとり、yを新しいx、余りを新しいyとする操作を余りが0になるまで繰り返すのはユークリッドの互除法である。終了時のxには最後に割り切れたときの除数が入っており、これがaとbの最大公約数になる。例えばa=12、b=18なら計算を追うと6が残る。

選択肢ごとの解説

• ア最小公倍数はa×b÷最大公約数で求めるもので、この手順では得られない。
• イ正解。ユークリッドの互除法により最大公約数が求まる。
• ウ素数を探す処理は含まれていない。
• エ商ではなく余りを使って繰り返している。

この問題に出た用語

• 流れ図
• ユークリッドの互除法

同じ分野の他の問題

• 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 問3
• A, B, Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、デ…2021年度 春期 問2
• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 問3
• 各ノードがもつデータを出力する再帰処理f(ノード n)を定義した。この処理を、図の2分木の根(最上位のノード)から始めた…2024年度 春期 問3
• あるデータ列を整列したら状態0から順に状態1、2、・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。 状態0 3…2023年度 秋期 問3