유클리드 호제법(Euclidean algorithm)

유클리드 호제법은 두 자연수 사이에 존재하는 최대 공약수를 빠르게 구하는 알고리즘이다.

---

최대 공약수

자연수 a와 b의 최대 공약수를 구하는 방법은 아래의 절차를 따른다.

예를 들어 176과 121의 최대 공약수를 구한다고 생각해보면 흐름은 아래와 같다.

1. 176를 121로 나눈다. 나누어 떨어지지 않는다. 나머지는 55
2. 121를 55로 나눈다. 나누어 떨어지지 않는다. 나머지는 11
3. 55를 11로 나눈다. 나누어 떨어진다. 따라서 최대 공약수는 11

 

소스코드로 표현해보면 아래와 같다.

public static int gcd(int a, int b) {
	return a%b==0 ? b : gcd(b,a%b);
}

 

---

최소 공배수

두 수의 곱은 최대 공약수와 최소 공배수의 곱과 같다 라는 관계식에 의해 최대 공약수를 구했다면 최소 공배수 또한 구할 수 있다.

$$a \times b = G \times L$$

$$L = \frac{a \times b}{G}$$

 

따라서 최소 공배수를 구하는 메서드는 아래와 같이 정의할 수 있다.

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

---

실행 결과

public class Main {
    public static void main(String[] args) {
        int a = 176;
        int b = 121;

        System.out.println("최대 공약수 : " + gcd(a,b));
        System.out.println("최소 공배수 : " + lcm(a,b));
    }

    public static int gcd(int a, int b) {
    	return a%b==0 ? b : gcd(b,a%b);
    }

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

최대 공약수 : 11
최소 공배수 : 1936