유클리드 호제법이란?

두 수의 최대 공약수를 구하는 알고리즘

호제법: 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다.

---

9와 3에 대한 최대 공약수 를 구한다고 가정해 보자

9 = 3 \* 3
3 = 3 \* 1
▷ 9와 3의 최대 공약수는 3

이렇게 작은 수에 대해서는 빠르게 소인수분해를 통해 최대 공약수를 눈으로 찾을 수 있지만, "1112와 695의 최대 공약수를 찾으시요" 같이 큰 수들의 최대 공약수를 찾는 문제가 나온다면 많은 시간이 소요될 것이다.

이를 위해 유클리드 호제법을 사용해 빠르게 최대 공약수를 찾는다.

유클리드 호제법을 이해하려면 MOD에 대한 부분을 이해해야 한다.

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

MOD 예시

1112 mod 695 = 417

유클리드 호제법은 위 MOD 연산의 결과 값이 0 이 나올 때 까지 반복하는 것이다.

1112 mod 695 = 417

695 mod 417 = 278

417 mod 278 = 139

278 mod 139 = 0

"0"이 된 순간의 직전 값 "139" 가 최대 공약수가 된다.

따라서 1112와 695의 최대 공약수는 139이다.

이는 417, 278, 139도 "모두 N의 배수인 수"라는 것과 같은 최대 공약수를 가진다는 것을 알 수 있다.

---

유클리드 호제법을 함수로 표현한다면 아래와 같이 표현할 수 있다.

작성: java

1. 반복문
public static int GCD(){
	int a = 1112;
    int b = 695;
    
    while(true){
    	int c = 0;
        
    	c = a % b;
        
        if( c == 0 ) {
        	return b;
            break;
        }
        else {
        	a = b;
            b = c;
        }
    }
}

2. 재귀
public static int GCD(int a, int b){
	return a % b == 0 ? b : GCD(b, a % b);
}

---

참고

https://velog.io/@yerin4847/W1-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95