[BOJ 2609번] 최대공약수와 최소공배수(JAVA) (feat. 유클리드 호제법)

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

2609번: 최대공약수와 최소공배수

// 유클리드 호제법
import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String args[]) throws Exception {

		String s[]=br.readLine().split(" ");
		int a=Integer.parseInt(s[0]);
		int b=Integer.parseInt(s[1]);
		System.out.println(getGCD(Math.max(a, b), Math.min(a, b)));
		System.out.println(getLCM(Math.max(a, b), Math.min(a, b)));

	}
	
	public static int getGCD(int a, int b) {
		while (b > 0)
	    {
	        int tmp = a;
	        a = b;
	        b = tmp%b;
	    }
	    return a;
	}
	
	public static int getLCM(int a, int b) {
		return a*b/getGCD(a, b);
	}
}

최대공약수와 최소공배수는 유클리드 호제법을 사용하면 쉽게 코드로 구현할 수 있습니다.

유클리드 호제법은 a와 b라는 두 수의 최대공약수를 구할 때 a를 b로 나눈 나머지를 구하고, b를 나머지로 나누고, 그 나머지를 구한 나머지로 나눠 나머지가 0이 될 때까지 반복해서 0이 되기 전에 나오는 마지막 나머지를 최대공약수로 결정하는 방법입니다.

유클리드 호제법을 이용해서 최대공약수를 구하는 예시를 들어보겠습니다.

예를 들어 10246과 954의 최대공약수를 구한다고 합시다,

10246=254*40+86

254=86*2+82

86=82*1+4

82=4*20+2

4=2*2+0

따라서 마지막 줄에서 나머지가 0이 되었을 때 0이 되기 전의 값이 2이므로 10246과 254의 최대공약수가 2임을 알 수 있습니다. 

따라서 이 알고리즘을 코드로 구현해보면 아래와 같습니다.

public static int getGCD(int a, int b) {
		while (b > 0)
	    {
	        int tmp = a;
	        a = b;
	        b = tmp%b;
	    }
	    return a;
	}

유클리드 호제법을 이용해서 최소공배수를 구하는 방법은 다음과 같습니다.

두 수 a와 b의 최소공배수를 구한다고 할 때, 두 수의 최소공배수=a*b/(a, b의 최대공약수)입니다.

따라서 이를 코드로 나타내면 아래와 같습니다.

public static int getLCM(int a, int b) {
		return a*b/getGCD(a, b);
	}

따라서 이 함수를 이용해서 문제를 풀면 위와 같이 풀 수 있습니다.