[프로그래머스] 최대공약수와 최소공배수

팁

최소공배수 = n*m/최대공약수

 

 

풀이방법

def numbers(n):
# n을 이루는 수 구하기
    i = 2
    res=[]
    while i <= n:
        if n%i==0:
            res.append(i)
            n = n//i
        else:
            i+=1
        
        if n == 1:
            break
            
    return res

def solution(n, m):
    n_res = numbers(n)
    m_res = numbers(m)
    
    common_num = set(n_res) & set(m_res) # 교집합
    all_num = set(n_res) | set(m_res) # 합집합
    
    # 최대 공약수
    ans1=1
    for i in common_num:
        ans1 *= i**min([n_res.count(i), m_res.count(i)])
    
    ans2=1
    # 최소 공배수
    for i in all_num:
        ans2 *= i**max([n_res.count(i), m_res.count(i)])
    
    return [ans1, ans2]

def solution(n, m):
    gcd = lambda a,b : b if not a%b else gcd(b, a%b)
    lcm = lambda a,b : a*b//gcd(a,b)
    return [gcd(n, m), lcm(n, m)]