[JAVA] 유클리드 호제법 - 최대 공약수 구하기

 

최대 공약수를 구하는 방법

 

일반적으로 최대 공약수를 구하려고 하면 소인수 분해를 이용해서 공통된 소수들의 곱으로 표현한다. 그러나 소인수 분해를 위해 소수를 먼저 찾아야 하고, 찾은 소수가 두개의 수를 공통적으로 나눌 수 있는지 확인해야 하기 때문에 이는 효율적이지 않다.  유클리드 호제법을 이용하면 더 간단한 방법으로 최대 공약수를 구할 수 있다.

 

 

유클리드 호제법(Euclidean Algorithm)

 

두 개의 자연수(두 개의 다항식)의 최대 공약수를 구하는 알고리즘이다. 

호제법이란 말은 두 수가 서로 상대방 수를 나누어 결국 원사는 후를 얻는 알고리즘을 나타낸다.   

 

 

2개의 자연수(또는 정식) a,b에 대해서 a를 b로 나눈 나머지를 r이라고 하면( 단, a>b )  a와 b의 최대 공약수는 b 와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r' 를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을때 나누는 수가 a 와 b 의 최대 공약수가 되는 것이다.

 

 

MOD 연산

 

유클리드 호제법을 수행하려면, MOD 연산을 이해하고 있어야 한다. MOD 연산이 최대 공약수를 구하는데 사용하는 핵심 연산이기 때문이다.  MOD 연산은 다음과 같다.

 

연산	기능	예제
MOD	두 값을 나눈 나머지를 구하는 연산	10 MOD 4 = 2 //10%4=2

 

MOD 연산은 다시 말해 두 값을 나눈 나머지를 구하는 연산이라 볼 수 있다. MOD 연산을 이용하면 유클리드 호제법을 구현할 수 있다.

 

 

1. 먼저 큰 수를 작은수로 나눈 나머지를 구한다. ( MOD 연산 )

270 MOD 192 = 78

//270 % 192 = 78 과 같다. ( 큰 수에서 작은수로 MOD 연산을 진행 )

2. 앞 단계에서 작은 수와 MOD 연산 결과값( 나머지 )으로  또 MOD 연산을 수행한다.

192 MOD 78 = 36 //192 % 78 =36

3. 위 과정을 반복해서 나머지가 0이 되면, 그 순간의 나누는 수를 최대 공약수로 선택한다.

78 MOD 36 = 6
36 MODE 6 = 0

//따라서 gcd(270,192) = 6

 

 

 

따라서 정리하자면

• 유클리드 호제법은 나눗셈만을 반복해서 최대공약수(GCD)를 구할 수 있다.
• 두 개의 수가 아무리 커도 정해진 순서로 계산하면 효율적으로 최대공약수를 구할 수 있다

 

이를 코드로 나타내면 다음과 같다.

    private int gcd(int a, int b) {
        if(b==0) return a;
        else return gcd(b, a % b);
    }

 

 

관련된 문제들 ( 발견하면 계속해서 추가 )

백준1934_ 최소공배수  (https://www.acmicpc.net/problem/1934)

백준1850_ 최대공약수 (https://www.acmicpc.net/problem/1850)

백준1033_ 칵테일 (https://www.acmicpc.net/problem/1033)

 

Referance

 

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

 

유클리드 호제법(Euclidean algorithm)