[자바] 유클리드 알고리즘(최대공약수 찾기)

유클리드 알고리즘(최대공약수 찾기)

최대 공약수란

최대공약수(GCD : Greatest Common divisor)는 고대 그리스의 수학자인 유클리드에 의해서 발견되었다.

최대 공약수란 주어진 두정수의 약수 중에서 가장큰 공통이 되는 약수를 말한다.

50 : 1, 2, 5, 10, 25, 50

20 : 1, 2, 4, 5, 10, 20

이두 정수의 공통되는 것은 1,2,4,10 이며 가장큰것 10이 최대 공약수가 되는것이다.

기본적으로 중학교때 배운 과정에서는 소인수분해를 하여서 최대공약수, 최대 공배수를 구할수 있다.

기본적인 이해는 끝이 났으니 유클리드의 알고리즘에 대해 알아보자.

유클리드의 알고리즘은 최대공약수의 성질을 이용하여 뺄셈과 두 값의 교환이라는 기본적인 동작으로만 최대 공약수를 구할 수 있다.

X=x*G(50=5*10)           Y=y*G(20=2*10)

최대 공약수는G가 되고 x,y는 서로소가 된다.

Y와 X-Y의 최대 공약수는 우찌 될까.

X-Y = x*G - y*G = (x-y)*G

x-y 와 y는 역쉬 서로소 이므로 최대공약수 역쉬 G가 된다.

GCD(x, y) = GCD(x-y, y)

최대 공약수는 정수의 순서에 관계없으므로

GCD(x,y) = GCD(y,x)

도 성립된다.

즉 50과 20의 최대 공약수는

GCD(50,20) = GCD(30,20) = GCD(10,20) = GCD(20,10) = GCD(10,10) = GCD(0,10) = GCD(10,0)

이 되어 최대 공약수는 10이 된다.

알고리즘을 간단히 정리하서 설명을 하면.

1.임의의 두정수 X와 Y를 입력을 받는다.

2. Y가 X보다 크다면 두수는 교환을 한다.

3. X에는 X-Y를 대입.

4. X가 0이면 Y가 최대 공약수 0이 아니면 2번부터 반복을 한다.

 

이러한 뺄셈에 대한 연속적인 결과는 값의 차이가 크게 난다면 (예를 들어 3000과 2의 최대 공약수를 구한다면?) 뺄셈에 대한 연산이 무쟈게 많아지게 된다.

이에대해 수학적으로 뺄셈에 대한 연속적인 결과값은 두수를 나눈뒤의 나머지의 값과 동일하다

이를 이용하면 반복적으로 계산하는 것을 줄일수가 있다.

GCD(X,Y) = GCD(X%Y, Y)  가 성립이 된다.

즉

GCD(50,20) = GCD(10,20) = GCD (20,10) = GCD(10,10) = GCD(0,10)

이 된다.

이를 이용하여 최대 공약수를 구하는 방법을 작성해보자.

1. 임의의 두정수 X와 Y를 입력 받는다.

2. Y가 0 이면 X가 최대 공약수 아니면 X=X%Y하고 X와 Y를 교환한다.