문제 📕

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

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

접근 방법 🧐

이전에 풀어봤던 문제인지라 바로 유클리드 호제법 으로 풀기 시작했다.

유클리드 호제법

검색해보면 아주 잘 설명해주신 분들이 많아서 내가 이해한 대로만 간단하게 써놓자면,

숫자 A 숫자 B가 있습니다.

A, B의 최대공약수는 r = A mod B의 값인 r과의 최대공약수와 같습니다.

- 나머지가 없다는 것은 공통된 약수로 떨어진다는 의미

예를 들어,
A = 69, B = 42이다
여기서 GCD는 최대공약수이다.

GCD(69,42) r = 27
GCD(42,27) r = 15
GCD(27,15) r = 12
GCD(15,12) r = 3
GCD(12,3) r = 0

최대공약수는 3

A = a 최대공약수, B = b 최대공약수 로 이루어져 있으며, a와 b는 서로소이다.

[최소공배수 = a * b * 최대공약수] 

A * B = a * 최대공약수 * b * 최대공약수 이므로
최소공배수 = (A * B) / 최대공약수

내가 쓴 코드 ✍️

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	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 num1 = Integer.parseInt(st.nextToken());
		int num2 = Integer.parseInt(st.nextToken());
		
		int maxNum = gcd(num1, num2); //최대공약수
		
		bw.write(maxNum+"\n");
		bw.write(num1*num2/maxNum+"");
		bw.flush();
		bw.close();
		
	}
	
	public static int gcd(int num1, int num2) {
		if(num2 == 0)
			return num1;
		return gcd(num2, num1 % num2);
	}
}