[Baekjoon] 최대공약수와 최소공배수

👀 문제 설명

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

 

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

예제 입력 1

24 18

 

예제 출력 1

6

72

 

✍🏻풀이

최대공약수는 유클리드 호제법을 이용해서 풀고, 최소공배수는 큰 수 * (작은 수 / 최대공약수)를 해서 구하면 된다.

유클리드 호제법은 다음 링크를 참고해 공부했다.

유클리드 호제법

 

코드

package boj;

// 최대공약수와 최소공배수 (https://www.acmicpc.net/problem/2609 )

import java.util.*;
import java.io.*;

public class BOJ_2609 {

	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());
		
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		// 최대공약수 - 유클리드 호제법
		int bigNum = Math.max(a, b);
		int smallNum = Math.min(a, b);
		
		while (smallNum != 0) {
			int mod = bigNum % smallNum;
			bigNum = smallNum;
			smallNum = mod;
		}
		
		// 최소공배수
		int gcd = bigNum;
		int lcm = a * b / gcd;
		
		bw.write(gcd + "\n" + lcm + "\n");

		bw.flush();
		bw.close();
	}

}