https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 난이도 : 브론즈 1 태그 : 수학, 정수론, 유클리드 호제법 유클리드 호제법 최소공배수와 최대공약수는 유클리드 호제법을 이용해 간단히 구할 수 있습니다. 최대 공약수 (GCD, Greatest Common Divisor) 유클리드 호제법은 명시적으로 기록된 가장 오래된 알고리즘으로써, 위키피디아에서는 이 알고리즘을 아래와 같이 설명하고 있습니다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약..