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

#문제

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

#풀이

유클리드 호제법을 사용한다. 

2개의 자연수의 최대공약수(GCD)를 구하는 알고리즘 이다.

자연수 a와 b (a > b)에서 a를 b로 나눈 나머지를 r이라고 했을 때

GCD(a, b) = GCD(b, r) 이며, r이 0이 되는 순간 b가 최대 공약수가 된다.

최소 공배수는 두 수를 곱한 후 최대 공약수로 나눠주면 구할 수 있다.

 

#소스코드

package math;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ2609 {

    public static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        sb.append(getGCD(a, b)).append("\n");;
        sb.append(a*b/getGCD(a, b)).append("\n");
        System.out.print(sb.toString());
    }

    public static int getGCD(int a, int b){
        if(b > a){
            int temp = a;
            a = b;
            b = temp;
        }
        while(b != 0){
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }

    public static void main(String[] args) throws Exception {
        input();
    }
}