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

 

 

제목: 최대공약수와 최소공배수

실버5

 

---

문제

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

입력

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

출력

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

---

예제 입력 1 복사

24 18

예제 출력 1 복사

6
72

---

 

 

 

🔑 코드

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

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 num1 = Integer.parseInt(st.nextToken());
		int num2 = Integer.parseInt(st.nextToken());
		int outNumber = GCD(Math.max(num1, num2), Math.min(num1, num2));
		StringBuilder sb = new StringBuilder();
		sb.append(outNumber+"\n").append(num1*num2/outNumber);
		System.out.println(sb);
		
	}

	static int GCD(int bigNumber, int smallNumber) {
		int r = bigNumber % smallNumber;

		if (r == 0) {
			return smallNumber;
		} else {
			return GCD(smallNumber, r); // 재귀
		}
	}
}

 

 

 

 

알고리즘 분류

• 수학
• 정수론
• 유클리드 호제법

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

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