JAVA 백준 2609번 최대공약수와 최소공배수

문제

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

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

24 18

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

6
72

알고리즘 분류

유클리드 호제법(euclidean), 수학(math), 정수론(number_theory)

힌트

a, b의 최소공배수는 절대값 a x b 를 최대공약수로 나눗값과 같다
a, b의 최대공약수는 절대값 a x b 를 최소공배수로 나눗값과 같다
최소공배수나, 최대공배수를 못구할경우 순환오류가 발생한다.
최대공약수는 유클리드 알고리즘으로 풀수있다. 두 양의정수 a>b 가정이 있으나
a<b일 때 a mod b ≡ a(a%b==a)이므로 Gcd(a,b)는 Gcd(b,a)를 호출하므로 자연스럽게 a와 b 위치가 바뀌게 된다.

int GCD(int a, int b)
{
    int r = a % b;
    if (r == 0) {
      return b;
    }
    return GCD(b, r);
}

소스코드

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 token = new StringTokenizer(br.readLine(), " ");
        int N = Math.abs(Integer.parseInt(token.nextToken()));
        int S = Math.abs(Integer.parseInt(token.nextToken()));

        int gcd = GCD(S, N);
        System.out.println(gcd);
        System.out.println((N * S) / gcd); // LCM
    }

    // greatest common divisor
    static int GCD(int a, int b) {
        if (b == 0) return a;
        return GCD(b, a % b);
    }

    // least common multiple
    static int LCM(int a, int b) {
        return (a * b) / GCD(a, b);
    }
}