코딩테스트/알고리즘

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

브라보서 2021. 8. 8. 18:38

- 최대공약수 -> Greatest Common Divider

- 최소공배수 -> Largest Common Divider

def gcd(a, b):
    if a > b :
        min = b
    else:
        min = a
    
    for i in range(min+1, 0, -1):
        if a % i == 0 and b % i == 0:
            gcd = i
            break
    return gcd

def lcm(a, b):
    if a > b :
        max = a
    else:
        max = b
    
    for i in range(max, a*b+1):
        if i % a == 0 and i % b == 0:
            lcm = i
            break
    return lcm

def solution(a, b):
    return [gcd(a,b), lcm(a,b)]

- 유클리드 호재법

def gcd(X, Y):
    while Y > 0:
        X, Y = Y, X%Y
    return X

def lcm(X, Y):
    return X*Y // gcd(X, Y)

def solution(a, b):
    return [gcd(a,b), lcm(a,b)]