백준 2609 문제 - 유클리드 호제법을 이용

백준 2609 문제이다

최소 공배수와 최대 공약수를 구하는 문제이다.

우리는 여기서 유클리드 호제법을 사용할 수 있다. 얼마 전 내가 유클리드 호제법 증명하는 것을올렸으니 한 번 찾아보자.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int a = scanner.nextInt();
        int b = scanner.nextInt();

        int g = gcb(a, b);
        System.out.println(g);
        System.out.println((a*b) / g);
    }

    public static int gcb(int a, int b) {
        if ( b == 0 ) {
            return a;
        }

        return gcb(b, a%b);
    }
}