次の流れ図の処理で、終了時のx に格納されているものはどれか。
ここで、与えられたa 、b は正の整数であり、mod(x , y )はx をy で割った余りを返す。
ア | a とb の最小公倍数 |
イ | a とb の最大公約数 |
ウ | a とb の小さい方に最も近い素数 |
エ | a をb で割った商 |
答え イ
【解説】
問題の流れ図は与えられた整数x , y に対しmod(x , y )を計算し、x にy を計算結果をyy に代入し、y が0になったときのx の値が示すものですが、この処理はユークリッドの互除法と呼ばれる最大公約数(イ)を求めるアルゴリズムになります。
【キーワード】
・ユークリッドの互除法