유클리드 호제법(JAVA)

최대공약수를 구할 때 사용되는 알고리즘으로 이를 활용한 알고리즘 문제들이 정말 많기 때문에

한번 정리하고 넘어가려 한다.

 

먼저 참조 문서를 보고 오겠다.

 

공부할땐 위키백과만한게 없다.

 

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

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

 

요약하자면 최대공약수를 구하려는 수 a ,b 가 있다면 (a > b)

 

그 두 수를 나눈 나머지가 있을경우 나머지로 더 작은수를 나누고 또 나머지가 생길 경우

이전의 나머지로 나머지를 나누기를 반복해 결국 나눠 떨어질때의 나누는 수가 곧 최대공약수가 된다는것이다. 

 

자세한 증명과정은 이미 위키백과에 잘나와있으니 증명하진 않고 바로 코드로 구현 해보겠다.

 

반복문을 이용한 방법과 재귀를 사용한 방법 두가지가 있는데

 

둘다 사용해 구현 해보도록 하겠다.

 

1) 재귀를 사용한 구현

 

	public int euclid(int a, int b) {
		if(b == 0) return a;
		return euclid(b, a%b);
	}

 

 

2) 반복문을 사용한 구현

 

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

 

단순히 현재 작은수로 큰수를 나눈 나머지를 작은수로, 이전의 작은수를 큰수로 갱신하며

나누어 떨어질때까지 연산하면 된다.

 

여기서 더 나아가 최소공배수를 구하는건 그냥 두수의 곱에서 두수의 최대공약수를 나누어주면 된다.

 

최대공약수 = a * b / euclid(a,b); // 단 (a > b)