유클리드 호제법 - 최대공약수 구하기 : 백준 13241번으로 알아보기

유클리드 호제법이란?

2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘이다.

호제법이라는 것은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다.

예시

12345 와 2445의 최대공약수를 구해보면, 다음과 같게 풀 수 있다.

12345 = 2445 x 5 + 125
2445 = 125 x 19 + 70
125 = 70 x 1 + 55
70 = 55 x 1 + 15
55 = 15 x 3 + 10
15 = 10 x 1 + 5
10 = 5 x 2

이에 따라 최대공약수는 5가 나오게 된다.

최소공배수 구하기

최소 공배수는 두 정수가 공통적으로 가지는 배수 중 가장 작은 값을 의미합니다.

정수 a와 b의 최대공약수 G에 대해서 아래의 식을 만족하는 정수 x와y가 존재할때,

a = Gx, b = Gy (단, x, y는 정수)

1. a b = GGxy
2. a b / G = GGxy / G (양변에 최소 공약수를 나누어 줌)
3. a b / G = Gx*y(최소공배수)
4. 최소공배수 = a * b / G

위와 같은 과정을 통해서 최소공배수는 a * b / G 를 만족함을 알 수 있습니다.

해당 방법을 통해서 백준의 13241번 문제를 풀어 봅시다.

문제

https://www.acmicpc.net/problem/13241

13241번: 최소공배수

풀이

import java.io.*;
import java.sql.Array;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        long c = a*b; // 최소 공배수는 a*b / 최대공약수 이다.

        //유클리드 호제법
        while (b > 0) {
            long temp = a;
            a = b;
            b = temp%b;
        }

        bw.write(String.valueOf(c/a));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

참고

https://tech.lonpeach.com/2017/11/12/Euclidean-algorithm/