[알고리즘] GCD & LCM

최대 공약수 (Greatest Common Divisor)와 최소 공배수(least common multiple)를 구한다.

 

알고리즘으로는  유클리드 호재법을 사용하여 해결합니다.

큰 수를 작은수로 나눈 나머지를 0이 될때 까지 계속 나눕니다.

 

글로 적으니 복잡하네요.

아래의 코드를 보면 

 

GCD

85를 51로 나눕니다.    -> 나머지 34

51을 34으로 나눕니다. -> 나머지 17

34를 17로 나눕니다.    -> 나머지 0 => 최대 공약수 : 17

 

LCM

두 수의 곱을 최대 공약수로 나눕니다.

 

=> 85 * 51 / 17 =  255

 

class Solution {

    @Test
    public void getGCD_LCD() {

        // given
        int x = 85;
        int y = 51;

        // when
        long gcd = getGCD(x, y);
        long lcd = getLCD(x, y, gcd);

        // then
        Assertions.assertEquals(17, gcd);
        Assertions.assertEquals(255, lcd);
    }

    public long getGCD(long x, long y) {
        long remain  = Math.max(x, y);
        long divider = Math.min(x, y);

         while(true) {
            remain = remain % divider;

            if(remain == 0) {
                break;
            }

            divider = divider ^ remain;
            remain  = divider ^ remain;
            divider = divider ^ remain;  // xor swap
        }
        return divider;
    }

    public long getLCD(long x, long y, long gcd ) {
        return x * y / gcd;
    }
}

 

 

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전