トップページ -> Pythonで数学をしてみよう! -> 最小公倍数・最大公約数を求めよう!

最小公倍数・最大公約数を求めよう!

今回は最小公倍数・最大公約数をテーマに考えてみたいと思います.

課題

2つの整数m,nの最小公倍数・最大公約数を求めるプログラムを書きたい.

最小公倍数・最大公約数はm,nの素因数分解が分かっていれば簡単に求めることができます. 第2回の素因数分解のプログラムが利用できそうです.


n = int(input())
m = int(input())

min_factor = [False for i in range(max(m,n)+1)]
min_factor[0] = True
min_factor[1] = True

# 最小の素因数を求める
for i in range(2,int(max(m,n)**0.5)+1):
    if min_factor[i] == False:
        p = i
        min_factor[i] = p
        for j in range(p*p,max(m+1,n+1),p):
            if min_factor[j] == False:
                min_factor[j] = p
                
for i in range(max(m,n)+1):
    if min_factor[i] == False:
        min_factor[i] = i
  
# 最小の素因数を使って素因数分解を行う
num_ = n
div_list_n = []
while n > 1:
    div_list_n.append(min_factor[n])
    n = int(n/min_factor[n])
    
num_ = m
div_list_m = []
while m > 1:
    div_list_m.append(min_factor[m])
    m = int(m/min_factor[m])
素因数分解はO(log(n))の計算量のプログラムでした. 次に以下のコードを使って,最小公倍数・最大公約数を求めます.

# LCM: 最小公約数 GCD:最大公倍数
GCD = []
for i in range(len(div_list_m)):
    factor = div_list_m[i]
    if factor in div_list_n: # 共通していればGCDの要素に追加
        GCD.append(factor)
        div_list_n.remove(factor)

gcd = 1
for i in range(len(GCD)):
    gcd *= GCD[i]
    
lcm = int(m_*n_/gcd) # m*nをgcdで割ればlcm

print(gcd,lcm)
素因数の数だけ繰り返し操作をしますが,素因数の個数は高々log(n)なので,計算量はO(log(n))ですね. アルゴリズム全体の計算量としてはO(log(n))となります. これを一つの関数にまとめたものが以下のコードです.

def gcd_lcm(m,n):
    m_ = m
    n_ = n
    min_factor = [False for i in range(max(m,n)+1)]
    min_factor[0] = True
    min_factor[1] = True

    # 最小の素因数を求める
    for i in range(2,int(max(m,n)**0.5)+1):
        if min_factor[i] == False:
            p = i
            min_factor[i] = p
            for j in range(p*p,max(m+1,n+1),p):
                if min_factor[j] == False:
                    min_factor[j] = p

    for i in range(max(m,n)+1):
        if min_factor[i] == False:
            min_factor[i] = i

    # 最小の素因数を使って素因数分解を行う
    num_ = n
    div_list_n = []
    while n > 1:
        div_list_n.append(min_factor[n])
        n = int(n/min_factor[n])

    num_ = m
    div_list_m = []
    while m > 1:
        div_list_m.append(min_factor[m])
        m = int(m/min_factor[m])

    # LCM: 最小公約数 GCD:最大公倍数
    GCD = []
    for i in range(len(div_list_m)):
        factor = div_list_m[i]
        if factor in div_list_n:
            GCD.append(factor)
            div_list_n.remove(factor)

    gcd = 1
    for i in range(len(GCD)):
        gcd *= GCD[i]
        
    lcm = int(m_*n_/gcd)

    print(gcd,lcm)
大きな数についてはエラトステネスの篩を応用したもののほうが速いかもしれませんが, そうでない数についてはこちらのほうが速いかもしれません. こちらはO(√n)の計算量です.

def prime_div(n):
    div_list = []
    n_ = n 
    div_num = 2 
    while div_num <= int(n_**0.5)+1:
        if n%div_num == 0:
            div_list.append(div_num)
            n = n/div_num 
        else:
            div_num += 1 
        if n < div_num:
            break 

    if n != 1:
        div_list.append(int(n))
        
    return div_list

def gcd_lcm2(m,n):
    m_ = m
    n_ = n
    
    div_list_m = prime_div(m)
    div_list_n = prime_div(n)

    # LCM: 最小公約数 GCD:最大公倍数
    GCD = []
    for i in range(len(div_list_m)):
        factor = div_list_m[i]
        if factor in div_list_n:
            GCD.append(factor)
            div_list_n.remove(factor)

    gcd = 1
    for i in range(len(GCD)):
        gcd *= GCD[i]
        
    lcm = int(m_*n_/gcd)

    print(gcd,lcm)
ここまでは素因数分解を行って最小公倍数・最大公約数を求めました. ですが,その難しさを根拠に暗号システムが作られるほどの素因数分解をするのは大変です. 素因数分解をせずに最小公倍数・最大公約数を求めることはできないのでしょうか?

ユークリッドの互除法

そこで登場するのがユークリッドの互除法です. まずは,そのアルゴリズムについて説明します.

ユークリッドの互除法

ユークリッドの互除法2

次々に割り算を行い問題を(a,b)→(b,r_1)→(r_1,r_2)→(r_2,r_3)の最大公倍数を求める問題へと簡単化していっています.
この割り算は高々log(a)回しか行われません. この操作は再帰関数を用いることで以下のように簡単に定義することができます.

def gcm(x,y):
    if y == 0:
        return x
    elif x == 0:
        return y
    else:
        if x >= y:
            return gcm(x%y,y)
        if x < y:
            return gcm(x,y%x)
      
x = int(input())
y = int(input())
print(gcm(x,y),int(x*y/gcm(x,y)))
O(log(n))の計算量ですが,リストを使わず割り算だけで求めている分,前の2つより高速です. 計算量のオーダー自体は同じなのでnを"十分に"大きくすれば同じくらいの速さに収束するのかもしれません(?) 数学をやっていると「高々有限」や「極限を取れば」と簡単に言いたくなりますが,コンピュータの世界で理論上の正しさを過信してしまうと痛い目にあいます. (学生時代に「極限取れば収束するんでしょ?」と情報系の教官に言ったら怒られました(苦笑))
次回はいくつかの方法でフィボナッチ数列の実装をします.

<- 前へ戻る 【目次に戻る】 次へ進む ->