問題1の気づき
この式を繰り返す。
ユーグリッドの互除法のことを知らなかった。
ユーグリッドの互除法
2つの自然数の最大公約数について、次の定理が成り立ちます。
割り算と最大公約数
2つの自然数 𝑎, 𝑏 について,𝑎 を 𝑏 で割ったときの商を 𝑞,余りを 𝑟 とすると
「𝑎 と 𝑏 の最大公約数」は,「𝑏 と 𝑟 の最大公約数」に等しい。
この割り算と最大公約数の定理を使って、2つの自然数の最大公約数を求める方法が、次の ユークリッドの互除法 です。
ユークリッドの互除法
次のように2つの自然数 𝑎, 𝑏 の最大公約数を求める方法を ユークリッドの互除法,または単に互除法という。
𝑎 を 𝑏 で割り,余り 𝑟 を求める
𝑏 を①で求めた余り 𝑟 で割り,その余り 𝑟1 を求める
𝑟 を②で求めた余り 𝑟1 で割り,その余り 𝑟2 を求める…
⋯⋯
この操作を繰り返すと余りが必ず0になる(割り切れる)。余りが0になったときの割る数が,求める最大公約数になる。
出典 https://rikeilabo.com/euclids-parity-method#1
気づき
算出された割った数で割ることを繰り返すことで最大公約数を求めることができるのか。
しかし
これも問題文を読み且つタイトルを見るとこれも再帰のことを言っていることに気づく。
これも問題の慣れが必要なのか。
出典