[유클리드 호제법] 최대공약수와 최소공배수

유클리드 호제법은 최대공약수를 구하는 알고리즘이다. 최대공약수를 구해서 최소공배수 까지 구할수 있다.

유클리드 호제법은 mod 연산을 통해 재귀함수 형식으로 구현한다.

 

두 개의 숫자 8,10이 있다고 가정하면

처음 두 값의 나머지 연산을 수행한다.

 

8 % 10 = 8

나머지 연산을 통해 나온 결과 값 8을 나누는 수로 넣어주고 처음 나누는 수를 나눠지는수에 넣어준다. 이렇게 다음 식은

 

10 % 8 = 2 가 된다. 그러면 또 똑같이 결과값 2를 나누는 수로 넣어주고 원래 연산에서 나누는 수를 나눠지는 수에 다시 넣어준다.

8 % 2 = 0  

이렇게 나머지가 0이 될때의 나누는 수가 두 숫자의 최대 공약수가 된다.최소공배수는 두 숫자를 곱해준 다음 최대공약수로 나누어준다면 구할 수 있다.

10 * 8 / 2 = 40

 

식을 정리해보면 아래와 같다.

8 % 10 = 8

      10  % 8 = 2

                  8 % 2 = 0

 

해당 식을 재귀함수 방식으로 구현 해보면 다음과 같이 나오게 된다.

public class Main {
    public static void main(String[] args) {
        int res = gcd(8,10); // 최대공약수
        int res2 = 8 * 10 / res; // 최소공배수
    }
    static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a%b);
    }
}

 

주어진 수가 하나라면 해당 수에 대한 최소공배수와 최대공약수는 결국 자기 자신이된다. 그렇다면 숫자가 3개 이상으로 주어진다면 어떻게 유클리드 호제법을 사용해야할까?

생각보다 간단하다. 처음 두수의 최대공약수를 구한뒤 구한 최대공약수와 다음 수와의 최대공약수를 구해주면 된다.

 

8 , 10 , 5 이렇게 3개의 숫자가 있다고 가정할때

8과 10의 최대공약수를 구한다. 과정은 위와 같기 때문에 구하면 2가 나온다.

그러면 나온 2와 5의 최대공약수를 구해준다.

 

2 % 5 = 2

      5 % 2 = 1

             2 % 1 = 0

세 수의 최대공약수는 1이 나오게 된다.

 

최소공배수 또한 마찬가지다. 앞의 두수의 최소공배수를 구한뒤 다음 수와의 최소공배수를 구하면 된다.

8,10의 최소 공배수는 40이므로 40과 5의 최소공배수를 구한다

 

40 % 5 = 0 두 수의 최대 공약수는 5이므로 두 수를 곱한뒤 최대공약수로 나눠주면

40 * 5 / 5 = 40

 

8,10,5 세 수의 최소공배수는 40이 된다.

 int answer = arr[0] * arr[1] / gcd(arr[0],arr[1])
 if(arr.length >= 3) {
    for(int i = 2; i < arr.length; i++) {
       answer = answer * arr[i] / gcd(answer,arr[i]);
    }
 }
 
 int gcd(int a, int b) {
 	if (b == 0) return a;
    return gcd(b, a % b);
 }