[알고리즘] 최대공약수(GCD), 최소공배수(LCM) - JAVA

15 Nov 2023 in TIL on 알고리즘

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

최대공약수(GCD)

GCD는 Greatest Common Divisor의 약자로 최대공약수이다.

두 수의 약수들의 공통된 값 중 최댓값을 말한다.

GCD를 구하는 방법을 알아보자.

1. BigInteger 내장 함수

private static int gcd(int a, int b) {
    BigInteger n = BigInteger.valueOf(a);
    BigInteger m = BigInteger.valueOf(b);

    return n.gcd(m).intValue();
}

1. 재귀

private static int gcd(int a, int b) {
    if(b == 0) {
        return a;
    }

    return gcd(b, a % b);
}

1. 반복문

private static int gcd(int a, int b) {
    int n = a;
    int m = b;

    if (a < b) {
        n = a;
        m = b;
    }

    int tmp;
    while (m != 0) {
        tmp = n % m;
        n = m;
        m = tmp;
    }

    return n;
}

최소공배수(LCM)

최소공배수는 구한 GCD를 이용해 구할 수 있다.

두 수 a와 b를 곱하고 최대공약수로 나눠주면 최소공배수가 된다.

private static int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}