유클리드 호제법(최대공약수 구하기)

유클리드 호제법

두개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.
호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이다.

작동 방식

78696과 19332의 최대공약수를 구한다고 해보자.

78696 ＝ 19332×4 ＋ 1368
    19332 ＝ 1368×14 ＋ 180
     1368 ＝ 180×7 ＋ 108
      180 ＝ 108×1 ＋ 72
      108 ＝ 72×1 ＋ 36
       72 ＝ 36×2 ＋ 0

나머지 정리를 통해 다음과 같이 표시할 수 있다.

나머지 정리란 A(원래 수) = B(나누는 수) * C(몫) + R (나머지) 로 다시 말해
78696 ＝ 19332×4 ＋ 1368 는 78696을 19332로 나누면 몫은 4이고 나머지는 1368이라는 이야기이다.

본론으로 돌아와 위와같이 유클리드 호제법이 동작하면 마지막에 최대공약수는 32가 된다.

알고리즘 구현 (자바)

public static int GCD(int x, int y){
		while(y!=0){
        	int r = x % y;
            x = y;
            y = r;
        }
        return x;
}

추가(최소 공배수)

참고로 최소 공배수는 x 와 y를 곱한 값에서 최대공약수를 빼주면 구할 수 있다.
알고리즘이 간단하니 살펴보면

public static int LCM(int x, int y){         
        return x * y / GCD(x , y); 
}