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

🔗 백준 2609 최대공약수와 최소공배수 https://www.acmicpc.net/problem/2609

문제

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

---

입력

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

---

출력

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

---

풀이

유클리드 호제법을 활용하여 코드를 구현하였다.

 

유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법은 두 수로 최대공약수를 구하는 유명한 알고리즘이다.

A와 B 수가 있고 A % B = C라고 할 때,

A, B의 최대공약수와 B, C의 최대공약수가 같다는 성질을 활용하여 계속적인 나눗셈으로 C가 0이 되었을때 나누는 수가 최대공약수가 된다.

 

내가 푼 코드

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

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());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int n = eucd(Math.max(a, b), Math.min(a, b));

        a /= n;
        b /= n;

        int res = a * b * n;
        System.out.print(n + "\n" + res);
    }

    // 유클리드 호제법
    private static int eucd(int big, int small) {
        int r = big % small;
        if (r == 0) return small;
        else return eucd(small, r);
    }
}