ユークリッドの互除法

「ユークリッドの互除法を使って２つの数字の最大公約数を求めるプログラム」

ユークリッドの互除法とうい法則をご存知だろうか。

一応Wikipediaを貼っておくが、ちとわかりづらい。

https://gyazo.com/cdb0125ae683a191cd8e946181c0becd

こっちの画像の方がよっぽど分かりやすい。

この画像の通り、２つの数の最大公約数を早く求めたいなら、大きい数を小さい数で割り、「割る数」をそのときの「余り」で割る。ということをくり返していき、余りが０になったときの「割る数」がその２つの最大公約数となるのである。

kadai12

「大きな数字と小さな数字を入力したら、その２つの数字の最大公約数を求めるプログラム」を組んでみよう。

code:ヒント

dai = int(input("大きな数を入れてちょ"))

sho = int(input("小さい数を入れてちょ"))

while ●●●●●●●●●●:

数字の入れ替え

print(●●●●●●●●●●)