[알고리즘/자바] 재귀 알고리즘으로 유클리드 호제법 구현하기

유클리드 호제법

---

크기가 큰 두 수가 있을 때 최대 공약수를 빠르게 구하기 위해서 사용한다.

 

유클리드 호제법은 A를 B로 나눈 나머지가 C일 때, (A와 B의 최대 공약수) = (B와 C의 최대 공약수)라는 사실을 이용해서 처음에 구하려고 했던 숫자의 크기를 점점 줄여 간단하게 만든 다음 최대 공약수를 구하는 방법이다.

 

예를 들어, 48과 21의 최대 공약수를 구해본다면.

48/21 ••• 6

21/6  ••• 3

6/3  ••• 0

최대 공약수는 3이 된다.

 

 

유클리드 호제법 메서드 구현

---

static int ea(int x, int y) {
	if (y == 0){
		return x;
	} else {
		return ea(y, x % y);
}

class EuclidGCD {
	static int ea(int x, int y) {
		if (y == 0) {
			return x;
		} else {
			return ea(y, x % y);
		}
	}

	public static void main(String[] args) {
		int x = 48;
		int y = 21;

		System.out.println("최대공약수는 " + ea(x, y) + "입니다.");
	}
}