[백준] 2609 최대공약수와 최소공배수

문제출처] https://www.acmicpc.net/problem/2609

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

---

문제요약

최대공약수와 최소공배수를 구하는 문제

풀이

최대공약수와 최소공배수를 구하는 중학교 때 배운 방법은 소인수 분해를 통한 방법이다.

그러나 소인수 분해를 이용하여 알고리즘을 작성할 경우 성능이 떨어지므로 유클리드 호제법을 이용하였다. 유클리드 호제법은 유키피디어를 참고하였다.

https://ko.wikipedia.org/wiki/유클리드_호제법

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

---

유클리드 호제법은 간단하게 구현할 수 있다.

GCD를 계산할 때 a가 항상 b보다 크게 유지되기 위하여 조건문을 통하여 통제해주었다. 

그 후 while문을 통하여 GCD에서 작은 수(b)가 0이 될 때까지 수행해준다.

---

소스코드는 Python 3으로 작성되었습니다.

import sys

input = sys.stdin.readline

n, m = map(int, input().split())


def gcd(a, b):
    # 무조건 a > b 유지
    if a > b:
        pass
    else:
        a, b = b, a

    while b > 0:
        r = a % b
        a, b = b, r

    return a


g = gcd(n, m)
l = n * m // g

print(g, l, sep='\n')