key word : 최대공약수, 최소공배수, 유클리드 호제법, GCD

처음엔 두 수를 소수로 일일이 나누어 ArrayList에 저장하고 중복되는 소수를 체크하며 최대공약수 최소공배수를 구하는 알고리즘을 구현했다.

당연히 잘 돌아가기는 하지만 좀 더 효율적인 솔루션이 있을 것 같아 더 찾아봤다.

유클리드 호제법과 재귀를 이용해 최대공약수를 쉽게 구할 수 있었고, 최대공약수를 구하면 최소공배수 또한 쉽게 구할 수 있었다.

개념

a > b 인 두 수의 최대 공약수를 구하기 위해서 r = a % b를 구하고, r’ = b % r을 구하는 것을 반복한다.

r’을 0으로 만드는 r이 바로 두 수의 최대공약수이다.

구현

재귀를 사용하면 쉽게 구할 수 있다. public int GCD(int a, int b){ if(b == 0) return a; return GCD(b, a % b); }

최소공배수

소인수분해를 한 결과에서 공통되는 것만 곱한 것이 최대공약수, 공통되는 것을 한 번씩만 곱하고 나머지를 곱한 것이 최소공배수였다.

즉 두 수의 곱을 최대공약수로 나누면 최소공배수라는 의미가 된다.

a * b / GCD(a, b);로 쉽게 구할 수 있다.