유클리드 호제법(Uclidean algorithm)

최대 공약수란? 주어진 정수들의 공통된 약수들 중 가장 큰 약수를 말한다.

 

최대공약수를 구하는 방법은 소인수 분해와, 유클리드 호제법이있다. 두가지 방법으로 192와 72의 최대 공약수를 구하는 방법을 살펴보자.

 

소인수 분해

소인수 분해로 구할 때는 먼저 주어진 수들을 각자 소인수 분해한다. 그 후에 중복되는 부분을 서로 곱해주면 최대 공약수를 구할 수 있다.

192 = 2^6 * 3 = 2 * 2 * 2 * 2 * 2 * 2 * 3
72 = 2^3 * 3^2 = 2 * 2 * 2 * 3 * 3

이때, 중복되는 2^3 * 3 = 2 * 2 * 2 * 3 = 24로 두수의 최대 공약수는 24이다.

 

유클리드 호제법

유클리드 호제법은 두 정수의 최대 공약수를 재귀적으로 구하는 방법이며 소인수 분해보다 훨씬 빠른 시간안에 최대 공약수를 구할 수 있다.

192 = 72 * 2 + 48 //192를 72로 나누어 나머지를 구한다.
72 = 48 * 1 + 24 //72를 위 연산의 나머지인 48로 나눈다.
48 = 24 * 2 // 48을 위 연산의 나머지인 2로 나누었더니 나머지가 0이다.

따라서, 나머지가 0이 되기전 연산의 나머지인 24가 두 수 의 최대 공약수라고 할 수 있다.

 

이를 알고리즘으로 구현하면 다음과 같다. 어떤 수 x, y(x > y)의 최대 공약수를 구해보자. - JavaScript로 구현

 

1. x, y 의 최대 공약수를 gcd(x, y)로 표기한다. 

2. y가 0이라면 최대 공약수는 x이다.

3. y가 0이 아니라면 gcd(y, x % y)로 구한다. 

function gcd(x, y) {

    if(y === 0) return x; //y가 0이면 x값 반환
    
    return gcd (y, x % y);
    
}

 

위의 코드를 x = 192, y =72로 실행시켜보면, 다음과 같은 과정을 거친다.

gcd(192, 72) = gcd(72, 48) = gcd(48, 24) = gcd(24, 0) = 24

 

 

조금 더 이해를 돕기위하여, 두 정수를 직사각형의 두 변의 길이라고 생각하면 두 정수의 최대 공약수를 구하는 문제를 다음 문제처럼 바꿀 수 있다.

두 변의 길이가 각 x, y(x > y)인 직사각형을 정사각형으로 완전히 채우려고 한다. 이렇게 채울 수 있는 정사각형의 가장 긴 변의 길이를 구하시오.

 

예를 들어 x = 22, y = 8인 직사각형이 있고 이를 정사각형으로 완전히 채울 때, 정사각형의 가장 긴 변의 길이를 구하는 과정은 아래와 같다.

따라서, 변의 길이가 2인 정사각형으로 위의 직사각형을 가득 채웠을 때, 빈공간이 없으므로 최대 공약수는 2이다.

 

 

+ '라메의 정리'라는 이론에 따르면 유클리드 호제법을 이용하여 나머지를 취하는 과정은 최악의 경우라도 두 수 중 작은 수를 십진법으로 표시한 자리수의 5배를 반복하기 전에 최대공약수에 이른다고 한다. 어쨌든 소인수 분해보다는 훨씬 빠르다는 의미인듯