문제 출처: https://www.acmicpc.net/problem/2609

문제 설명

두 수의 최소공배수와 최대공약수를 찾는 문제

입력

24 18

출력

6
72

문제 풀이

import java.io.*;
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 a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int high = a > b ? a : b;
        int low = a < b ? a : b;
        while(high % low != 0) {
            int remainder = high % low;
            high = low;
            low = remainder;
        }
        bw.write(low + "\n");
        bw.write(a * b / low + "\n");
        br.close();
        bw.flush();
        bw.close();
    }
}

정수론의 유클리드 호제법을 적용해서 최대 공약수를 구했다. [유클리드 호제법]

최소공배수는 최대공약수가 나오면 쉽다. ( a * b / a 와 b의 최대공약수)