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

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

---

입력

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

출력

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

---

예제 입력 1

24 18

예제 출력 1

6
72

---

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

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int r = a > b ? gcd(a, b) : gcd(b, a);
        bw.write(r + "\n" + (a * b / r));
        br.close();
        bw.flush();
        bw.close();
    }

    public static int gcd(int p, int q)
    {
       if (q == 0) return p;
       return gcd(q, p % q);
    }
}

최대공약수는 유클리드 호제법을 사용하였다.

 

최소공배수는 두 수를 곱하고 최대공약수로 나눈 수이다.