ユークリッドの互除法とは

2つの自然数の最大公約数を求める方法の1つ

使いどころ

互除法のやり方

「割り切るまで二つの自然数を割り続ける」やり方を説明する。
①「2つの自然数のうち大きい数÷小さい数」する。
②前の手順の除数(最初は「2つの自然数のうち小さい数」)を前の手順の余りで割る。
③以上の手順を余りが0になるまで繰り返す。
余りが0のときの除数が最大公約数である。

※最大公約数とは余りが0になる上に一番大きな「割り切る整数(約数)」で一番大きな「割る方も割られる方も割ることが出来る数(公約数)」
※除数は割る方の数の事である。a÷bのbの方。

正式な言い方は調べると出ます。
私が噛み砕いて理解する分には上記の※の文章になります。

pythonで表現するユークリッドの互除法

a,b=(int(x) for x in input().split())#数字にするため。input(),input()だと判定が駄目みたい

#再帰関数(自分自身を呼び出す関数)
def gcd(a, b):#gcdは最大公約数(greatest common divisor)の略
    if b == 0:#このifは二つの自然数aとbが最初から余り0を導き出すことができるもの。
        return a
    else:
        return gcd(b, a%b)#ifのようにa,bの段階で0が出せない時の処理をこれにしている。
print gcd(a,b)

ちなみに：最小公倍数

上記の方法で2つの自然数の最小公倍数も求めることができる。
あくまで、最大公約数を求めるためのユークリッドの互除法を「最小公倍数を求めること」にも使えるという方法であることを認識してほしい。

a,b=(int(x) for x in input().split())#数字にするため。input(),input()だと判定が駄目みたい

#再帰関数(自分自身を呼び出す関数)
def gcd(a, b):#gcdは最大公約数(greatest common divisor)の略
    if b == 0:#このifは二つの自然数aとbが最初から余り0を導き出すことができるもの。
        return a
    else:
        return gcd(b, a%b)#ifのようにa,bの段階で0が出せない時の処理をこれにしている。

print a*b/gcd(a,b)