BOJ 2609 : 최대공약수와 최소공배수

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

풀이

앞의 약수에서 참고한 알고리즘인 '유클리드 호제법'을 조금만 참고하면 된다. 

두 수의 최대 공약수는 두 수의 나머지를 계속 나눔으로써, 언젠가 나누어 떨어지는 수를 의미한다. 그리고 최소 공배수는 두 수의 최대 공약수로 구성된 최소의 수 이므로 x(a를 최대공약수로 나눈 수)*y(b를 최대공약수로 나눈 수)*GCD(a,b)로 귀결된다. 이는 두 수(a = x* GCD(a,b), b = y*GCD(a,b))로 구성 되어 있기 때문에 각각의 최소 공배수는 위와 같이 구성된다.

최대공약수(GCD : Greatest Common Divisor)

최소공배수(LCM : Least Common Multiple)

import sys

if __name__ == '__main__':
    data = list(map(int, sys.stdin.readline().split()))
    
    a, b = max(data), min(data)
    while b > 0:
        a, b = b, a%b

    print(a)
    c, d = max(data), min(data)

    print(c * d // a)