백준 - 2609번(최대공약수와 최소공배수)

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

문제

• 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        System.out.println(gcd(N, M));
        System.out.println(N * M / gcd(N, M));
    }

    private static int gcd(int N, int M) {
        if (M == 0) {
            return N;
        }

        int temp = N;
        N = M;
        M = temp % M;
        return gcd(N, M);
    }

}

• 유클리드 호제법과 최소공배수를 빠르게 구하는 법을 알아보았다.