유클리드 호제법(Euclidean Algorithm)

유클리드 호제법의 기능부터 살펴보자면 2개의 자연수에 대해서 최대공약수(GCD)를 구하고 이를 바탕으로 최소공배수(LCM)를 구할 수 있다.

두 수 A, B에 대해서 큰수 A를 작은 수 B로 나누는데 이때 나머지가 0이면 작은 수가 최대공약수이다.

만약 나눠떨어지지 않으면 B를 A/B의 나머지로 다시 나눈다. 이때 나눠 떨어지면 A/B의 나머지가 최대공약수가 된다.

이 과정을 나눠떨어질 때까지 반복을 하는데 간단히 보자면 두 수를 서로 나누는 과정을 나눠떨어질 때까지 반복하고 나눠떨어질 때 나누는 수가 최대공약수가 된다.

 

유클리드 호제법을 간단히 예시를 통해 풀이해보자면...

 

1. 다음과 같이 두 수가 주어진다.

231, 84

 

2. 이 두 수를 유클리드 호제법을 이용하면

231를 84로 나누면 나머지는 63.

84를 63으로 나누면 나머지는 21.

63을 21로 나누면 나머지는 0.

 

3. 그러므로 최대공약수는 21이 되고, 최소공배수는 다음과 같을 때,

231 = 21 * 11

84 = 21 * 4

이므로 최소공배수는 (231 * 84) / 21 = 924

 

이를 코드로 구현하면 다음과 같다.

 

import java.io.*;

class Main{
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int A = Integer.parseInt(br.readLine());
        int B = Integer.parseInt(br.readLine());
        int GCD= gcd(A, B);
        int LCM = A * B / GCD;
        System.out.println("최대공약수: "+ GCD + '\n'+"최소공배수: "+ LCM);
    }

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

            else return gcd(b, a % b);
        }
        else return gcd(b, a);
    }
}