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

- GCD -> 유클리드 호제법으로 풀 수 있다.

https://st-lab.tistory.com/154

최대 공약수가 구해지면, 최소 공배수는 두 수의 곱 / 최대 공약수이다.

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

public 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 N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int mx = Math.max(N, M);
        int mn = Math.min(N, M);
        while(mn != 0) {
            int r = mx % mn;
            mx = mn;
            mn = r;
        }
        System.out.println(mx);
        System.out.println(N*M/mx);
    }
}