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

내 풀이

유클리드 호제법을 사용하여 풀이

• 최대공약수(Greatest Common Divisor):

1. a를 b로 나눈 나머지(단, a>b) = r
2. a와 b의 최대공약수 = b와 r의 최대공약수
3. b를 r로 나눈 나머지 r1을 구하고, 다시 r을 r1로 나눈 나머지를 구하는 과정을 반복해 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수

• 최소공배수(Least Common Multiple):

1. 최소공배수 = 두 자연수의 곱/최대공약수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int x = a*b;
        int max = Math.max(a, b);
        int min = Math.min(a, b);

        int gcd;
        int lcm;
        int mod = 1;

        while (mod != 0) {
            mod = max % min;
            max = min;
            min = mod;
        }

        gcd = max;
        lcm = x/gcd;

        System.out.println(gcd);
        System.out.println(lcm);
    }
}