유클리드 호제법

유클리드 호제법

유클리드 호제법(Euclidean algorithm)은 두 수의 최대공약수(GCD)를 효율적으로 구하는 고대의 알고리즘입니다. 이 방법은 두 수를 계속해서 나눗셈과 나머지 연산을 반복함으로써 최대공약수를 찾는 방식입니다.

 

 

*코딩테스트 준비용 알고리즘 학습을 위한 것이기 때문에 수학적 증명은 생략하겠씁니당

 

 

유클리드 호제법의 과정

다음과 같은 단계로 유클리드 호제법을 통해 최대 공약수를 구할 수 있습니다.

1. 두 수 a, b를 MOD
2. b와 나머지로 MOD
3. 나머지가 0이 되는 순간의 b가 최대 공약수

 

 

 

최소공배수 lcm는 gcd를 이용하여 구하는 것이 일반적입니다.

 

아래에 반복문을 이용하여 최소공배수와 최대공약수를 구하는 함수를 작성하였습니다.

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        StringBuilder result = new StringBuilder();
        for(int i=0; i<t; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            result.append(lcm(a, b))
                    .append("\n");
        }

        System.out.println(result);
    }

    /*
     * 최대 공약수 구하기
     * 유클리드 호제법으로 풀이
     * 1. a에서 b로 나누기
     * 2. b에서 나머지로 나누기 -> 이 때 b를 a로, mod를 b로 자리를 옮겨주면 됨
     * 3. 나머지가 0이 될 때 까지 반복, 나머지가 0일 때 b가 답
     * */
    public static int gcd(int a, int b) {
        while (a % b != 0) {
            int mod = a % b;
            a = b;
            b = mod;
        }
        return b;
    }

    /*
    * 최대공약수 구하기
    * LCM(a,b)= ∣a×b∣ /  GCD(a, b)
    * */
    public static int lcm(int a, int b) {
        return Math.abs(a * b) / gcd(a, b);
    }
}

​

아래처럼 재귀를 통해서 구현할 수도 있습니다

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