[JAVA/자바] 백준 2609번: 최대공약수와 최소공배수

문제 풀이 프로그래머스에서도 똑같은 문제를 풀었었다! 유클리드 호제법을 사용한 최소공약수 구하기 문제~~ 자주 나오니 외워두는 게 좋을 거 같다.

GCD(a,b) = GCD(b, a%b) 이 성립한다. a = 24, b = 18 일때 GCD(24,18) = GCD(18, 6) = GCD(6, 0) = 6으로 최대 공약수는 6이 나온다. 이때 24 = 4 x 6, 18 = 3 x 6 (6은 최대 공약수, 4와 3은 서로소) 에서 최소 공배수는 4 x 3 x 6이므로 (24 x 18) / 6 으로 구할 수 있다.

그러므로 최대 공약수는 GCD(a,b)로 구하고 최소 공배수는 a x b / GCD(a,b) 로 구한다. 출처 https://www.acmicpc.net/problem/2609...