Baekjoon 2609번 최대공약수와 최소공배수

문제

https://www.acmicpc.net/problem/2609

걸린 시간

01 : 41 : 33

풀이

Python3

def factorizer(A, B):
    for divisor in range(2, max(A, B)+1):
        if A % divisor == 0 and B % divisor == 0:
            A = A // divisor
            B = B // divisor
            return A, B, divisor 
    return A, B, 0

if __name__ == "__main__":
    A, B = map(int, input().split())
    lcd = [] # lowest common divisor

    # 두 수가 서로소가 될 때 까지 최소공약수로 나눈다.
    while True:
        A, B, divisor = factorizer(A, B)
        # 나눈 수(제수)가 없을 때 종료
        if divisor == 0:
            break
        else:
            lcd.append(divisor)

    # 나누었던 최소공약수들을 모두 곱한게 최대공약수
    gcd = 1
    for i in lcd:
        gcd *= i     
    print(gcd)

    # 최대공약수에서 소수가 된 두 수까지 곱한 것이 최소공배수
    print(gcd * A * B)

손으로 최대공약수, 최소공배수를 구하는 과정을 그대로 구현했다. 문제를 다 풀고보니 유클리드 알고리즘이라고 몇줄 안되는 코드로 간단하게 해결하는 방법도 있었다.