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

문제

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

입력

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

출력

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

예제 입력 1

24 18

예제 출력 1

6
72

풀이

최대공약수 : gcd(a, a%b) 유클리드 호제법을 통해 최대공약수를 구할 수 있다.

호제법 : 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘.

a 를 b로 나눈 나머지를 r 이라고 했을 때 GCD(a,b) = GCD(b,r)과 같다. 여기서 r이 0 이면 b가 최대공약수가 된다.

$\gcd(24,18)=\gcd(18,6)=\gcd(6,0)=6$

최소공배수 : $L = lcm(a, b)$ 은 $L= lcm(a, b)= a * b / gcd(a, b)$ 이 성립

나머지가 0이 될 때까지

두 수 a,b의 공약수는 b와 a mod b의 공약수와 같다. 예제 24와 18에서는 24 mod 18=6, 18 mod 6=0이므로 마지막 0이 아닌 수 6이 최대공약수다. 매 반복에서 두 번째 수가 작아지므로 언젠가 종료한다. 코드의 remainder를 구한 뒤 a←b, b←remainder로 바꾸는 순서가 중요하다.

최소공배수는 a×b/최대공약수다. 24와 18이라면 (24/6)×18=72가 된다. 먼저 나눈 뒤 곱하면 중간 곱셈이 불필요하게 커지는 것을 줄일 수 있다. 입력은 각각 10,000 이하라 결과가 int 범위에 들어가지만, 코드에서는 long으로 승격해 일반적인 큰 값에도 덜 취약하게 했다.

기존 예시의 24와 16 계산은 문제 입력 24와 18을 설명하지 못했고, 재귀 보조 함수는 long 인수를 int 함수에 넘겨 컴파일되지 않았다. 제출 코드는 실제 사용하는 반복형 함수 하나로 정리했다. 시간은 유클리드 알고리즘의 O(log min(a,b)), 추가 공간은 O(1)이다. 두 수가 같으면 최대공약수와 최소공배수도 그 수가 된다.

나머지 규칙은 공약수의 집합이 유지되기 때문에 성립한다. d가 a와 b를 모두 나누면 a−qb도 나누므로 d는 a mod b를 나눈다. 반대로 d가 b와 a mod b를 나누면 a=(a div b)×b+(a mod b)도 나눈다. 따라서 두 쌍의 최대공약수가 같다.

한 수가 다른 수의 배수라면 첫 나머지가 곧 0이 된다. 예를 들어 12와 4는 최대공약수 4, 최소공배수 12다. 두 수가 서로소이면 최대공약수는 1이라 최소공배수는 두 수의 곱이다. 이 두 경우가 식과 구현의 간단한 경계 점검이 된다.

소스코드

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

public class Main {
    static int gcd(int a, int b) {
        while (b != 0) {
            int remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int greatest = gcd(a, b);
        long least = (long) a / greatest * b;
        System.out.println(greatest);
        System.out.println(least);
    }
}