[알고리즘] 백준 2609 - 최대공약수 최소공배수

분류 : 수학

1. 문제

https://www.acmicpc.net/problem/2609
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

2. 입력

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

3. 풀이

1) 최대공약수, 최소공배수

최대공약수(Greatest Common Divisor) : 가장 큰 공통된 약수
최대공배수(Least Common Multiple) : 가장 작은 공통된 배수

2) 유클리드 호제법

두 수 a, b ∈ ℤ 이고, r = a mod b 이라고 할 때(r은 a에 b를 나눈 나머지를 의미)
이 때 r은 (0 ≤ r < b) 이고, a ≥ b 이다.

이 때 a와 b의 최대공약수를 (a,b)라고 할 때 (a,b)의 최대공약수는 (b,r)의 최대공약수와 같다.

GCD(a,b) = GCD(b,r)

ex) GCD(56,35) = GCD(35,21) = GCD(21,14) = GCD(14,7) = GCD(7,0) = 7

3) 풀이

GCD(a,b) = GCD(b,r)을 이용해 재귀함수를 호출하는 구조로 작성한다.

4. 코드

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

public class GCD_2609 {

    static int gcd;

    public static void solution() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");

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


        if(a>b)
            GCD(a,b);
        else
            GCD(b,a);

        System.out.println(gcd);
        System.out.println(a*b/gcd);

    }

    public static void GCD(int a, int b){

        if(b!=0)
            GCD(b,a%b);
        else
            gcd = a;
    }
}