[백준] 자바 2609 최대공약수와 최소공배수

문제

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

입력

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

출력

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

---

테스트 케이스

입력:

24 18

 

출력:

6

72

 

---

접근

두 수를 입력하면 해당 수들의 최소 공배수와 최대 공약수를 구하는 문제입니다.

예전 알고리즘 수업시간에 유클리드 호제법에 대해 학습한게 기억나서 쉽게 풀 수 있었습니다.

두 수 a,b가 있을 때,

b값을 a위치에 넣고

a% b값을 b위치에 넣고

ex) a=24 b=18  --> a=18 b=6 --> a=6 b=0(b가 0이 되었으므로 종료)

b가 0이 될 때까지 이 과정을 반복하면 그때의 a값이 최대 공약수입니다.

초기 a*b에다가 최대공약수로 나누면 그것이 최소 공배수가 됩니다.

이를 코드로 구현하니 문제가 해결되었습니다.

---

코드

import java.awt.desktop.SystemEventListener;
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

	/*
 	 2609 problem
	*/

	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		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 result = gcd(a,b);
		bw.write(String.valueOf(result+"\n"));
		bw.write(String.valueOf(a*b/result));
		
		bw.flush();
		br.close();
		bw.close();
	}
	static int gcd(int a,int b) {
		if(b==0) {
			return a;
		}
		return gcd(b,a%b);
	}
}

---

주의

유클리드 호제법을 모른다면 그것 먼저 학습하자!

ㅇ0ㅇ