[Java] 최대공약수와 최소공배수

1. 문제 설명

두 자연수의 최대 공약수와 최소 공배수를 계산하는 프로그램을 작성해보자.

입력 형식

첫 줄에는 테스트케이스의 수 T가 1이상 100이하의 자연수로 주어진다.

이후 총 T줄에 걸쳐서 한 줄에 하나의 테스트케이스에 대한 입력이 주어진다.

각 테스트케이스의 입력은 한 줄에 두 자연수가 공백으로 구분되어 주어진다.
각 자연수는 1이상 10억이하의 자연수이다.

출력 형식

각 테스트케이스마다 두 줄에 걸쳐 결과를 출력한다.

각 테스트케이스의 첫 줄에는 테스트케이스의 번호를 Case #%d: 형식으로 출력한다. 대소문자와 공백에 주의한다.
두 번째 줄에는 최대 공약수와 최소 공배수를 공백으로 구분하여 순서대로 출력한다.

2. 알고리즘 접근

최대 공약수 : 공약수 중 가장 큰 값 (약수를 구하는 방식으로 풀이 가능)
최소 공배수 : 값1 x 값2 / 최대공약수
즉 최대 공약수를 이용하면 최소공배수를 구할 수 있다.

최대공약수 구하기

    private static int getGCD(int num1, int num2) {
        int min = Math.min(num1, num2);

        for (int i = min; i >= 1; i--) { 
        // 가장 큰값부터 찾아나가서 공약수가 나오면 최대공약수
            if (num1 % i == 0 && num2 % i == 0)
                return i; // 가지치기
        }
        return 1;
    }

위와 같이 구하는 것을 가장 쉽게 생각할 수 있다
but 문제의 시간복잡도를 고려한다면 옳지 않다 >유클리드호제법을 사용하자

유클리드 호제법

1. b가 a의 약수라면 b는 최대 공약수가 된다 ex) a = 24, b = 6 -> GCD = 6
2. 그렇지 않다면 A와 B의 최대공약수는 B와 (A%B)의 최대공약수와 같다
   = a % b != 0이라면 GCD(a, b) = GCD(b, a%b) -> 재귀 접근

3. 소스코드

package algorithm.comon.chapter4;

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

public class Q4C {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static long getGCD(int a, int b) {
        if(a % b == 0){
            return b;
        }
        return getGCD(b, a % b);
    }


    private static void testCase(int caseIndex) throws IOException{
        StringTokenizer st = new StringTokenizer(br.readLine());
        int num1 = Integer.parseInt(st.nextToken());
        int num2 = Integer.parseInt(st.nextToken());
        long gcd = getGCD(num1, num2);
        long lcm = (long)num1 * num2 / gcd;

        System.out.printf("Case #%d:\n", caseIndex);
        System.out.printf("%d %d\n", gcd,lcm);
    }

    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(br.readLine());

        for(int caseIndex = 1; caseIndex <= t; caseIndex++){
            testCase(caseIndex);
        }

    }
}