유클리드 호제법(Euclidean Algorithm)

유클리드 호제법이란?

두 개의 정수 혹은 다수의 자연수에서 최대공약수를 구하는 알고리즘이다.

유클리드

유클리드에 의해 기원전 300년 경에 발견된 가장 오래된 알고리즘이다.

호제법이란?

두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘

---

알고리즘

두 정수 A와 B의 최대공약수는 A와 B를 나누어 떨어지게 하는 수 중에서 가장 큰 정수 라는 사실을 기반으로 접근한다

큰 수를 작은 수로 나누어 떨어지게 한 뒤, 수를 반복적으로 수행하여 나머지가 0이 될 때까지 작동하는 방법 👉 이 때, 작은 수가 최대공약수이다

---

최대공약수 구하는 방법

1) 재귀 방식으로 구현

• b가 0이라면, a가 최대공약수가 되며, 그렇지 않으면 b와 a % b의 최대 공약수를 구한다
• 이를 재귀적으로 반복해서 최대공약수를 구할 수 있다

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

2) 반복문 방식으로 구현

• 먼저, b가 0이 될 때까지 a를 b로 나눈 나머지를 b에 대입하고, a와 b의 값을 교환한다
• 이를 반복하여 최대공약수를 구할 수 있다

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

최소공배수 구하는 방법

• 최대공약수의 함수를 기반으로 최소공배수를 구한다
• 최소공배수는 두 수의 곱에 최대공약수를 나눈 값과 같다
• 함수 내부에서 a와 b의 최대공약수를 이용하여 최소공배수를 구한다

public int lcm(int a, int b) {
	return a * b / gcd(a, b);
}