【Python】最大公約数と最小公倍数を求めるプログラムを紹介【ユークリッドの互除法】

本記事では、Pythonで2つの数の最小公倍数と最大公約数を求めるプログラムを書いたので、紹介します。

最小公倍数と最大公約数を求めるプログラム

順番に試していく方法

仕様

片方の数から順番に試して、両方の数を割り切れる数を探す

小さい方の数から始めることで、実行時間の短縮を測っている。

最小公倍数は公式に当てはめて求める。

ソースコード

num1=684
num2=1134

#最大公約数
def gcd(a,b):
    if(b>a):
        a,b=b,a
    i=b
    while i>0:
        if(a%i==0 and b%i==0):
            return i
        i-=1

#最小公倍数
def lcm(a,b):
    return int(a*b/gcd(a,b))

print(gcd(num1,num2))
print(lcm(num1,num2))

ユークリッドの互除法

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

ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）は、2 つの自然数の最大公約数を求める手法の一つである。

2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。

引用：Wikipedia

ユークリッドの互除法を使ったプログラム

num1=684
num2=1134

#ユークリッドの互除法
def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

#最小公倍数
def lcm(a,b):
    return int(a*b/gcd(a,b))

print(gcd(num1,num2))
print(lcm(num1,num2))

まとめ

今回は、ユークリッドの互除法を使ったやり方と、一つずつ順番に試して探す方法の2種類で最大公約数を求めた。

最小公倍数は公式に当てはめれば簡単に求められるのでとても楽でよかった。