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

문제

두 수의 최대공약수와 최소공배수를 출력하는 문제이다.

코드

import sys

def gcd(x,y):
    if(x%y == 0):
        return y
    else:
        return gcd(y, x%y)
a,b = map(int, sys.stdin.readline().split())
if(b > a):
    a, b = b, a
c = gcd(a,b)
print(c)
print(int(a*b/c))

풀이

최소공배수는 유클리드 호제법을 사용하였다.
두 자연수 a, b가 있을때,
a = b * x + Y 이면
a,b의 최소공배수는 a,Y의 최소 공배수와 같다.

Y와 a의 최소공배수가 C라고 하면
a = b x + C y 로 나누어지기 때문이다.

두 자연수의 곱은 최소공배수와 최대공약수의 곱이므로
두 수를 곱해서 최대공약수로 나누어 주었다.

두 수 A,B가 있다고 하면
A = xa, B = xb (x는 최대공약수)
AB = xaxb = x xab = 최대공약수 * 최소공배수