[2609] 최대공약수와 최소공배수 (JAVA)

# 문제 설명

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

---

입력

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

---

출력

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

 

# 정답 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int n1 = Integer.parseInt(st.nextToken());
        int n2 = Integer.parseInt(st.nextToken());

        int gcd = GCD(n1, n2);
        sb.append(gcd + "\n");

        //최소 공배수 = 두 수의 곱 / 최대공약수
        sb.append(n1 * n2 / gcd);

        System.out.print(sb);
    }

    //최대 공약수
    public static int GCD(int a, int b) {
        int big = Math.max(a, b);
        int small = Math.min(a, b);
        int result = 0;

        while (true) {
            result = big % small;

            if (result == 0) {
                return small;
            }

            big = small;
            small = result;
        }
    }
}

 

유클리드 호제법으로 최대 공약수를 구했다.

a와 b 중 큰 숫자를 big에, 작은 숫자를 small에 저장한다.

% 연산 결과값을 저장할 result를 만든다.

 

big % small의 결과값을 result에 저장한다.

만약 result가 0이면, 마지막 계산 식에서 작은 수를 리턴한다.

big은 small로, small은 result로 설정하고 위 과정을 반복하여 최대 공약수를 구한다.

 

최소 공배수는 두 수의 곱을 최대 공약수로 나누면 구할 수 있다.