유클리드 호제법

호제법(互除法)

互 : 서로 호
除 : 덜 제
法 : 법 법

공약수를 구하는 법칙

유클리드 호제법(Euclidean Algorithm)

고대 그리스 수학자 유클리드가 고안한 알고리즘 중 하나로, 두 수의 최대공약수(greatest common divisor) 를 구하는 알고리즘입니다.

핵심 개념

$a$ 와 $b$, 그리고 $a$를 $b$로 나눈 나머지 $r$이 있을 때, $a$와 $b$의 공약수는 $b$와 $r$의 공약수와 같다.
즉, $GCD(a,b) = GCD(b,r)$ 이 성립한다.

유도과정

8 x 6 크기의 직사각형이 있습니다.

8 x 6 크기의 직사각형에 6 x 6 크기의 정사각형을 채워넣으면, 2 x 6 크기의 공간이 남게 됩니다.

2 x 6 크기의 공간을 2 x 2 크기의 정사각형으로 채울 수 있기 때문에.

8 x 6 크기의 직사각형은 2 x 2 크기의 정사각형으로 채워질 수 있습니다.

위 예제처럼, 8과 6의 최대공약수는 6과 2(8을 6으로 나눈 나머지)의 최대공약수와 같다는 것을 알 수 있습니다.

최종 정리

$a$와 $b$의 공약수가 $b$와 $r$의 공약수와 같다는 것을 이용해, $a$ 와 $b$가 나누어떨어질때 까지 나누기를 반복하여 마지막에 남는 값이 a와 b의 공약수가 된다.

구현 코드

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