정수론 : 유클리드 호제법

유클리드 호제법

두 수의 최대 공약수를 구하는 알고리즘

 

1. 큰 수를 작은 수로 나누는 MOD 연산 수행

2. 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)로 MOD 연산 수행

3. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택

 

 

예) 270과 192의 최대 공약수를 유클리드 호제법을 사용해 찾아보자.

 

-> 재귀의 형태로 구현하여 사용한다.

---

 

백준 온라인저지 1934번

import java.util.Scanner;

public class P1934_최소공배수구하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();
        for (int i = 0; i < num; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();

            /**
             * A와 B가 주어졌을 때 최소공배수는
             * "A * B / 최대공약수"로 구할 수 있음
             * -> 유클리드 호제법을 이용해 최대공약수를 구한 후 두 수의 곱에서 최대공약수를 나눠주면 됨
             */

            int gcdNum = gcd(A, B); // 최대공약수
            int result = A * B / gcdNum;
            System.out.println(result);
        }
    }
    
    private static int gcd(int A, int B) {
        if(B == 0) {
            return A;
        } else {
            return gcd(B, A % B);
        }
    }
}