알고리듬 - 최대 공약수 & 최소 공배수 구하기(유클리드 호제법)

최대 공약수(GCD: Greatest Common Divisor)와 최소 공배수(LCM: Lowest Common Multiple)

를 구하는 방법에 대해 알아보자.

 

유클리드 호제법

유클리드 호제법(Euclidean-Algorithm)은 주어진 두 값의 최대 공약수를 구하는 알고리듬이다.

계산은 MOD 연산(%)을 활용한다.

 

진행 과정은 아래와 같다.

1. 주어진 두 값 중 큰 값을 작은 값으로 MOD 연산한다.

2. 앞의 과정에서 작은 값을 MOD 연산의 결과로 MOD 연산한다.

3. 결과가 0이 나오면 종료한다.

 

아래는 120과 34의 최대 공약수를 구한 예이다.

 

구현

내용이 어렵지 않아 바로 구현해 보았다.

 

전체 코드

package practice;

public class GCD {
    public static void main(String[] args) {
        gcd(120, 34);
        gcd(123, 456);
    }

    static void gcd(int n1, int n2) {
        int max = Math.max(n1, n2);
        int min = Math.min(n1, n2);

        int result = 0;
        do {
            result = max % min;
            max = min;
            min = result;
        } while(result != 0);

        System.out.println(n1 + ", " + n2 + "의 최대공약수 : " + max);
    }
}

큰 값을 max, 작은 값은 min에 담고 MOD 연산 결과가 0이 될 때까지 while문을 돌린다.

결과는 다음과 같다.

 

최소 공배수는 입력받은 두 값을 곱한 후 최대 공약수로 나누면 된다.

lcm = max * min / gcd