[Python] 최대 공약수와 최소 공배수

주어진 두 수의 최대 공약수와 최소 공배수를 우선 각각의 수를 소인수분해를 해야한다. 소인수분해란 1보다 큰 자연수를 소수의 곱으로 표현한 것이다.

 

# 소인수분해 (while문이 핵심)
def factorization(n):
    result = [0]*n
    result[1] = 1
    
    if n == 1:
        return result
    
    while n > 1:
        for i in range(2, n+1):
            if n % i == 0:
                result[i] += 1
                n = n//i
                break
    return result

 

 

최대 공약수(GCD)

두 수의 공통된 약수 중 가장 큰 약수를 의미한다. 소인수분해 이후 공통된 소인수들이 있을 것인데 그 중 지수가 작은 값을 선택하여 곱하여 구한다.

 

 

최소 공배수(LCM)

두 수의 공통되는 배수 중 가장 작은 배수를 의미한다. 소인수분해 이후 지수들이 높은 값을 선택하여 곱하여 구한다.

 

소인수분해의 지수를 이용한 GCD, LCM 구현

def solution(n, m):
    fact1 = factorization(n)
    fact2 = factorization(m)
    
    GCD = 1
    LCM = 1
    for i in range(len(fact1)):
        n1 = fact1[i]
        n2 = fact2[i]
        
        if n1 != 0 and n2 != 0:
            GCD = GCD * i**min(n1, n2)
            LCM = LCM * i**max(n1, n2)
        elif n1 == 0 or n2 == 0:
            LCM = LCM * i**max(n1, n2)
    return [GCD, LCM]

 

재귀함수를 이용한 GCD 구현과 LCM, GCD의 관계

수학적인 공식으로 관계를 표현하자면 아래와 같다.

LCM = GCD * (a/GCD) * (b/GCD)

 

재귀함수를 이용한 GCD와 수학 공식을 이용한 LCM을 구하는 코드이다.

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(a, b):
    n = gcd(a, b)
    return n * (a/n) * (b/n)

print(gcd(10, 12)) # 2
print(gcd(12, 18)) # 6
print(lcm(3, 4)) # 12
print(lcm(12, 18)) # 36