유클리드 호제법에 대해서

유클리드 호제법

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

gcd(a, b) = gcd(b, a % b)

 

이걸 반복하다가

gcd(x, 0) = x

 

가 되면 끝임

 

 

자바 기준 로직

public int gcd(int a, int b) {
	while(b != 0) {
    	int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

---

직접 계산해보기

 

40과 60의 최대공약수를 구한다고 해보자

그럼 gcd(40, 60)에 대해서 계산해봐야한다

 

첫번째 반복

60은 0이 아니므로 while문을 따라가면

int temp = 40 % 60 - > 40

a = b - > a = 60 (a = 60, b = 60)

b = temp (b = 40)

return a (a = 60)

한번 돌렸을 때 gcd(40, 60) 이 gcd(60, 40)이 되어있다

 

 

두번째 반복

gcd(60, 40)에 대해서 40 != 0이므로

temp = 60 % 40 - > 20 (temp = 20)

a = b - > a = 40 (a = 40, b = 40)

b = temp (b = 20)

return a (a = 40, b = 20)

두번째 반복에서 gcd(60, 40)이 gcd(40, 20)이 되어있다

 

 

세번째 반복

gcd(40, 20)에 대해 40 != 0 이므로

temp = 40 % 20 -> 20 (temp = 20)

a = b - > a = 20 (a = 20)

b = temp (b = 20)

return a (a = 20, b = 20)

세번째 반복에서 gcd(40, 20)이 gcd(20, 20)이 되어있다

 

 

네번째 반복

gcd(20, 20)에 대해 20 != 0이므로

temp = 20 % 20 -> 0 (temp = 0)

a = b - > a = 20 (a = 20)

b = temp (b = 0)

return a (a = 20, b = 0)

네번째 반복에서 gcd(20, 20)이 gcd(20, 0)이 되어있다

 

 

다섯번째 반복

gcd(20,0)에 대해 0 != 0은 거짓이므로 while문을 벗어나게 되어 반복하지 않는다.

따라서 60과 40의 최대공약수는 20이고, 그 결과 해당 메서드는 return값으로 20을 갖게 된다

---

해당 로직의 핵심 성질

a = b * k + r

 

수학 공부할때 배웠던 항등식

 

이 식의 특징

a와 b를 나눌 수 있는 수는 마찬가지로 r도 나눌 수 있다

a와 b를 각각 나누어서 나머지가 0이 되게끔 할 수 있는 수는 마찬가지로 c 또한 나누었을 때 나머지가 0이 된다는 의미

 

60과 40의 최대공약수를 구하는 로직에 대해 60 = 40 + 20 이라고 한다면

60과 40, 20을 모두 나누어 떨어지게 하는 수가 최대공약수이고, 그것이 20이다