基本情報技術者 一問一答｜B 第197問

解説

ユークリッド互除法は「大きい数を小さい数で割った余りで置き換える」操作を余りが0になるまで繰り返し、最後の除数が最大公約数（GCD）となるアルゴリズムである。gcd(24,36)では、①36÷24=1余り12なのでgcd(24,36)=gcd(12,24)、②24÷12=2余り0となり、余りが0になった時点の除数12が最大公約数で正解である。素因数分解でも24=2×2×2×3、36=2×2×3×3で共通部分は2×2×3=12と検算できる。6は公約数ではあるが最大ではなく、18は36の約数だが24を割り切れず、24は36を割り切れないため誤りである。頻出ポイントは余りで置き換える手順のトレースと「余りが0になったときの除数が答え」という終了条件であり、科目Bの定番アルゴリズムとして繰返し出題される。