프로그래머스 최대공약수와 최소공배수(java)

문제설명

생각하기

1. 최대공약수를 구한다.
2. 최대공약수를 가지고 최소공배수를 구한다.
3. 유클리드 호제법을 이용한다.

내 풀이

유클리드 호제법은 역사가 깊은 수학공식 중 하나로 최대공약수와 최소공배수를 구할 수 있는 공식이다.

유클리드 호제법
두 양의 정수 a,b (a>b)에 대하여 a = bq + r ( 0 <= r < b)라 하면,
a,b의 최대공약수는 b, r의 최대공약수와 같다. 즉,
gcd(a,b) = gcd(b,r)
r= 0 이라면 a,b의 최대공약수는 b가 된다.

이를 활용하여 Math함수로 n ,m의 크기를 비교하고
최소공배수의 공식인 a*b / 최대공약수를 사용해 코드를 짰다.
반복문으로 사용하는 방법도 있지만 재귀함수로 사용하는게 이해가 더 쉽고 코드도 간결하다.