자바 - 최대공약수(GCD), 최소공배수(LCM)

코테 문제를 풀다가 정말정말 오랜만에 본 단어들이다. 최대공약수, 최소공배수.
자바에서는 어떻게 구할 수 있는지 한 번 알아보자.

최대공약수(GCD)

BigInteger의 gcd 함수

BigInteger a = 15;
BigInteger b = 5;

BigInteger gcd = a.gcd(b);

• BigInteger 에는 최대공약수를 구하는 gcd함수가 있다.
• 요 함수를 사용하면 아주 쉽게 구할 수 있다.

재귀를 사용한 gcd 함수 구현

public int getGcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return getGcd(b, a % b);
    }
}

• 재귀를 이용해서 간단하게 구현할 수 있어서 위의 메서드와 둘 중 하나를 선택해서 사용하면 될 것 같다.

최소공배수(LCM)

최소공배수는 더더욱 간단하게 구현할 수 있다.
두 수를 곱하고 거기서 최대공약수로 한 번만 나줘주면 된다.

int a = 3;
int b = 15;
int lcm = a * b / getGcd(a, b);

쉽다!