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

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

課題

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

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])

# 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)

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)

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)

ユークリッドの互除法

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

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)))