2609.최대공약수와 최소공배수

문제

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

입력

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

출력

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	101506	58454	47498	57.836%

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

풀이

최대공약수 알고리즘 (GCD)

Greatest Common Divisor 는 가장 큰 공통된 약수라는 의미를 가진다. 일반적으로 최대공약수 문제를 풀때

"A와 B 두 수가 주어지면 A의 약수들을 모두 구하고, B의 약수들을 모두 구한 뒤 공통 된 약수들만 찾아내어 약수들의 곱으로 다시 나타내준다."

다음과 같은 방식으로 문제를 풀어왔다. 하지만 인수분해 하는데 시간이 많이 들고, 두수를 비교하여 곱해주는데 시간을 소비하게 된다.

최대공약수를 구하는 알고리즘을 이해하기 위해서는 유클리드 호제법(互除法) 을 이해해야한다.

두 수 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)

예를들어 146과 64가 주어졌다고 생각해보자.

• **GCD(146, 64) = GCD(64, 18) = GCD(18, 10) = GCD(10, 8) = GCD(8, 2) = GCD(2, 0) = 2

이렇게 구해지고 결과적으로 최대공약수 2가 구해진다.

이를 알고리즘으로 구성하는 방법은 2가지가 있다.

• 반복문을 사용
• 재귀를 사용

최소공배수 알고리즘(LCM)

Least Common Multiple / Lowest Common Multiple 은 최소공배수, 즉 공배수 중 최소인 수를 찾는것이다. 최소공배수 또한 알고리즘을 적용하면 쉽게 구할 수 있다.

a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수로 나눈것과 같다.

즉 순서는 다음과 같다.

1. 최대공약수를 구한다.
2. 두수의 곱과 구해진 최대공약수를 나눠준다.

위의 최대공약수를 구한과정에 대입해서 예시를 풀게 되면 다음과 같다.

계산과정

• a 와 b의 곱을 구한다. a = 24, b=18 a x b = 432
• a 와 b의 곱과 a와 b의 최대공약수를 나눠준다. 432 / 6 = 72
• 최소공배수는 72

코드

두가지 방법을 적용해서 문제를 풀어보자.

BufferedReader + 반복문

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

public class Main {

    public static void main(String[] args) throws IOException {

        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 d = gcd(a, b);

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

    }

    // 최대공약수 반복문 방식
    public static int gcd(int a, int b) {

        while (b != 0) {
            int r = a % b; // 나머지를 구해준다.

            // GCD(a, b) = GCD(b, r)이므로 변환한다.
            a = b;
            b = r;
        }
        return a;
    }
}

BufferedReader + 재귀

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

public class 최대공약수와최소공배수 {  

public static void main(String[] args) throws IOException {  
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  

String[] arr = br.readLine().split(" ");  

int a = Integer.parseInt(arr[0]);  
int b = Integer.parseInt(arr[1]);  

//최대공약수(gcd) 
int gcd = gcd(a, b);
//최소공배수(lcm)
int lcm = lcm(a,b,gcd);  

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

br.close();  
}  

static int gcd(int a, int b){  //최대공약수 구하기

if(b == 0){  
return a;  
}  
  //gcd(a,b) = gcd(b,r) 이므로.
return gcd(b, a % b);  
}  

static int lcm(int a, int b, int gcd){  

int result = a*b;  

return result / gcd;  
}  
}