유클리드 호제법(Euclid-algorithm)

백준 1934번 문제를 풀다가 유클리드 호제법이라는 개념을 알게되어서 정리해두려 한다.

호제법

두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘.

유클리드 호제법

두 개의 정수 혹은 다수의 자연수에서 최대공약수를 구하는 알고리즘.

사용하는 이유

일반적으로 두 수의 최대공약수(GCD)를 구하려면, 각각의 수를 소인수분해하고 공통된 소수를 찾으면 된다.
하지만, 해당 방법은 수가 커질수록 소인수분해가 어려워진다는 단점이 있다.
유클리드 호제법을 사용하면 조금 더 효율적으로 GCD를 구할 수 있다.

사용법

우선 MOD연산에 대해 알아야한다.

---

• MOD연산 : 두 값을 나눈 나머지를 구하는 연산

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

   1071 % 1029 = 42

2. 나눴던 작은 수와 나머지로 다시 MOD연산을 한다.(계속 반복)

   1029 % 42 = 21
   42 % 21 = 0

3. 나누어 떨어지면 해당 수가 최대 공약수이다.

   21이 최대 공약수

---

이런식으로 MOD연산을 반복적으로 수행하면 유클리드 호제법이 된다.

코드 _ Java

• 반복문 사용

public static int gcd(int a, int b) {
     while (b != 0) {//b가 0이 될 때까지
         int r = a % b;//a를 b로 나눈 나머지 r을 구한다.
         a = b;//b의 값을 a에 할당한다.
         b = r;//r의 값을 b에 할당한다.
     }//while end
     return a;//b가 0이 되었을 때, a는 최대공약수가 된다.
}//gcd end

• 재귀함수 사용

public static int gcd(int a, int b){
	return b ? gcd(b, a%b) : a;
}//gcd end