[백준] 2609번 : 최대공약수와 최소공배수

📍 문제

💡 접근

유클리드 호제법으로 문제를 풀었다.

1. 최대공약수 (GCD: Greates Common Divisor)

유클리드 호제법(Euclidean algorithm)
a, b 의 최대공약수 == b와 a%b의 최대공약수
=> GCD(a, b) = GCD(b, a%b)
a%b가 0이 될 경우 해당 b가 최대공약수이다.

ex ) GCD(581, 322) = GCD(322, 259) = GCD(259, 63) = GCD(63, 7) = GCD(7, 0) = 7
-> 마지막에 a%b가 0이 되었기 때문에 24와 18의 GCD는 6이다.

유클리드 호제법으로 최대 공약수를 구하는 방법 2가지
// 최대공약수 반복문 방식
int gcd(int a, int b) {
	
	while(b != 0) {
		int r = a % b;	// r = a mod b
       
		// GCD(a, b) = GCD(b, r)이므로 변환한다.
		a = b;		
		b = r;
	}
	return a;
}

// 최대공약수 재귀 방식
int gcd(int a, int b) {
	if(b == 0) return a;
	// GCD(a, b) = GCD(b, r)이므로 (r = a % b)
	return gcd(b, a % b);
}

2. 최소공배수 (LCM: Least Common Multiple)

최소공배수는 유클리드 호제법을 이용해 구한 최대공약수를 이용해 쉽게 구할 수 있다.
수학적으로 최대공약수와 최대공배수의 곱은 두 수의 곱과 같다.

최대공약수 x 최소 공배수 = 두수의 곱
=> LCM(a,b) = (a * b) / GCD(a, b)

// 최소공배수
int lcm(int a, int b) {
	return a * b / gcd(a, b);
}

👩‍💻 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
 
		int d = gcd(a, b);	
 
		System.out.println(d); // 최대공약수
		System.out.println(a * b / d); // 최소공배수
 
	}
 
	public static int gcd(int a, int b) {
		if (b == 0)
			return a;
		return gcd(b, a % b);
	}
}  

🔗 링크

https://www.acmicpc.net/problem/2609
참고 : https://st-lab.tistory.com/154