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

문제

- 두 개의 자연수(10,000이하의 자연수) 입력

- 최대공약수와 최소공배수 출력

 

해결방법

유클리드 호제법을 이용하여 두 개의 자연수에 대한 최대공약수를 구하였다.

유클리드 호제법의 원리는 다음과 같다. 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 한다면, a, b의 최대공약수와 b, r의 최대공약수는 같다. 이 성질에 따라서 a를 b로 나눈 나머지 r을 구하고, b를 r로 나눈 나머지를 구한다.

나머지가 0이 될 때 나눈 수가 a, b의 최대공약수가 된다. 

최소공배수는 "(a * b) / 최대공약수"로 구할 수 있다.

 

코드

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

class Main{
    public static void main(String[] args) throws Exception {
       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 gcd = getGCD(A, B);		// 최대공약수
       int lcm = (A * B) / gcd;		// 최소공배수

        System.out.println(gcd);
        System.out.println(lcm);
    }

    static int getGCD(int a, int b){
        if(a % b == 0){			// 0이 되었다면 나눈 수가 최대공약수
            return b;
        }
        return getGCD(b, a % b);	// 0이 될 때까지 나머지 구하는 과정 계속 반복
    }
}