[알고리즘/백준] 2609 최대 공약수와 최소 공배수 - 자바(Java), 유클리드 호제법

문제

https://www.acmicpc.net/problem/2609

풀이 코드

• 유클리드 호제법을 사용하여 최대 공약수(GCD)를 구한다. -> 유클리드 호제법 설명(위키백과)
• 최소 공배수(LCM)는 유클리드 호제법으로 구한 최대 공약수를 사용하여 풀이한다. -> LCM = n1 * n2 / GCD

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

public class Main {

    //유클리드 호제법으로 최대 공약수 구하기
    public static int gcd(int p, int q) {
        if (q == 0) {
            return p;
        }

        return gcd(q, p%q);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n1 = Integer.parseInt(st.nextToken());
        int n2 = Integer.parseInt(st.nextToken());

        int gcd = gcd(n1, n2);

        System.out.println(gcd);

        //최소 공배수(LCM) : n1*n2/GCD
        System.out.println(n1*n2/gcd);
    }
}