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

문제 📕

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

(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);
    }
}