[백준 2609번] 최대공약수와 최소공배수 - 파이썬

문제 링크: https://www.acmicpc.net/problem/2609

문제

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

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

---

이문제는 유클리드 호제법을 알고 있으면 쉽게 풀 수 있다.

최대공약수를 쉽게 구할수 있는 알고리즘이며, 두 수 a, b(a>b)가 있다고 할때, a와 b의 최대 공약수 G는 b와 a%b의 최대공약수 G'과 서로 같다

예를 들어
gcd(24,18)=gcd(18,6)=gcd(6,0)
여기서 b가 0이 되는 순간의 6이 최대공약수가 됨

이렇게 최대 공약수를 구했다면, 최소 공배수는 바로 구할수 있는데 A*B/gcd(a,b)를 해주면 최소 공배수가 된다. 이 수가 최소 공배수인 이유는 이 수를 A로 나눠도 떨어지고 B로 나눠도 나누어 떨어지는 수중에서 가장 작은수이기 때문

---

a,b=map(int,input().split())
A,B=a,b

while b!=0:
  a=a%b
  a,b=b,a

print(a) # 최대공약수
print(A*B//a) #최소공배수