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

選択肢

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

正解と解説

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

xをyで割った余りをtとし、x←y、y←tを繰り返してy=0で止める処理は、ユークリッドの互除法そのものである。終了時のxには、a と b の最大公約数が残る。

選択肢ごとの解説

• ア最小公倍数はa×b÷最大公約数で別途求める必要があり、この処理では得られない。
• イ正解。剰余を繰り返す互除法により最大公約数が求まる。
• ウ素数の判定や探索は行っていない。
• エ商ではなく余りを使って繰り返すため、商は残らない。

この問題に出た用語

• 流れ図（フローチャート）
• ユークリッドの互除法

同じ分野の他の問題

• fact(n)は，非負の整数nに対してnの階乗を返す。fact(n)の再帰的な定義はどれか。2025年度 春期 午前 問7
• 0≦x≦1の範囲で単調に増加する連続関数f(x)がf(0)<0≦f(1)を満たすときに，区間内でf(x)=0であるxの値…2025年度 春期 午前 問2
• 整列方法に関するアルゴリズムの記述のうち、バブルソートの記述はどれか。ここで、整列対象は重複のない1から9の数字がランダ…2024年度 春期 午前 問7
• 正の整数Mに対して、次の二つの流れ図に示すアルゴリズムを実行したとき、結果xの値が等しくなるようにしたい。aに入れる条件…2024年度 春期 午前 問5
• あるデータ列を整列したら状態0から順に状態1、2、・・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。2023年度 秋期 午前 問6