21.03.25 - [BOJ] 2609. 최대공약수와 최소공배수

[suhyunsim]

문제

• 2609

핵심 아이디어

• GCD = g, LCM = l
• g: a % b를 계속해서 b에 나눠서 나머지가 0 이되는 값 (유클리드 호제법 이용)
• l: g * (a / g) * (b / g) = (a * b) / g

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q2609;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int g = gcd(a, b);
        int l = (a * b) / g;
        System.out.println(g);
        System.out.println(l);
        sc.close();
    }

    private static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x % y);
        }
    }
}