백준 2609 최대공약수와 최소공배수 (Java)

1. 문제 링크

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

 

2. 문제 및 입출력예제

 

3. 문제 풀이

최대공약수는 유클리드 호제법을 이용하면 된다.

큰 수 A, 작은 수 B의 경우, B와 A%B 값을 재귀함수로 돌리면 A%B가 0이 되는 순간의 B가 최대공약수이다.

또한 A x B = 최대공약수 x 최소공배수라서 최소공배수는 A * B / 최대공약수로 구할 수 있다.

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] num = br.readLine().split(" ");
		int A = Integer.parseInt(num[0]);
		int B = Integer.parseInt(num[1]);

		if (B > A) {
			int temp = B;
			B = A;
			A = temp;
		} 
		
		int max = gcd(A,B);
		System.out.println(max);
		System.out.println(A*B/max);
	}

	private static int gcd(int a, int b) {
		if(a%b == 0) {
			return b;
		}
		return gcd(b, a%b);
	}
}