ユークリッドの互除法: 余りで最大公約数を見つけよう
ユークリッドの互除法は、2つの数の最大公約数を、割り算の「余り」を使ってすばやく見つける方法です。
たとえば、縦48cm、横18cmの長方形を、同じ大きさの正方形タイルでぴったり埋めたいとします。そのときの最大サイズを探すイメージです。
ルール
- 大きい数を小さい数で割る
- 余りを出す
- 「小さい数」と「余り」で同じことをくり返す
- 余りが0になったときの割る数が最大公約数
図で見る
コピペ用コード
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
print(gcd(48, 18))
AOJで挑戦してみよう！
学んだレシピを実際に使って、ジャッジから「Accepted（正解）」を勝ち取ろう！