최대공약수와 최소공배수

핵심 아이디어

n과 m의 큰 수와 작은 수를 구하여, x에는 작은 수의 약수들을 넣는다.

x에 포함되는 수중에서 큰 수와 나눠지는 수 중에서 가장 큰 값을 최대 공약수로 구한다.

그리고 두 수의 곱은 최소공배수 x 최대공약수를 사용하여, 최소공배수를 구한다.

첫 코드

def solution(n, m):
    x = []
    y = []
    answer = []
    temp = [n, m]
    a = min(temp)
    b = max(temp)
    for i in range(1, a+1):
        if a % i == 0:
            x.append(i)
    for j in x:
        if b % j == 0:
            y.append(j)
    gcd = max(y)
    lcm = int((m * n) / gcd)
    answer.extend([gcd, lcm])        
    return answer

개선 코드 1

def solution(n, m):
    answer = []
    temp = [n, m]
    a = min(temp)
    b = max(temp)
    x = [i for i in range(1, a+1) if a % i == 0]
    y = [j for j in x if b % j == 0]
    gcd = max(y)
    lcm = int((m * n) / gcd)
    answer.extend([gcd, lcm])        
    return answer

List Comprehension으로 좀 더 간략하게 개선해 보았습니다.

개선 코드 2

import math
def solution(n, m):
    answer = []
    a = math.gcd(n, m)
    b = int(n*m/a)
    answer.extend([a, b])
    return answer

math library를 사용하여 최대공약수와 최소공배수를 구할 수 있습니다. math.lcm()는 파이썬 3.9부터 사용 가능하므로, 두수의 곱은 최대공약수 X 최소공배수를 활용하여 최소공배수를 구하였습니다.