次の流れ図の処理で、終了時の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 の値が示すものですが、この処理はユークリッドの互除法と呼ばれる最大公約数(イ)を求めるアルゴリズムになります。
【キーワード】
・ユークリッドの互除法
- ユークリッドの互除法
2つの自然数(整数)の最大公約数を求める手法。
2つの数(自然数、整数)aとb(a ≥ b)について、aのbによる剰余をrとすると、aとbの最大公約数はbとrの最大公約数に等しいという性質が成り立ち、この性質を利用して最大公約数を求める方法。
もっと、「ユークリッドの互除法」について調べてみよう。
戻る
一覧へ
次へ