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

문제 링크 : https://www.acmicpc.net/problem/2609

---

이문제는 입력 받는 두 수의 최대 공약수와 최소 공배수를 구하는 문제이다. 

최대 공약수는 두 개 이상의 수가 공통으로 가지는 약수 중 가장 큰 수를 말한다.

두 수 18과 24가 있다 하면 각각의 약수는 다음과 같다.

18의 약수 : 1, 2, 3, 6, 9, 18

24의 약수 : 1, 2, 3, 4, 6, 8, 12, 24

이들 약수중에 공통으로 가지는 약수는 {1, 2, 3, 6}이고 이들 중 가장 큰 수는 6이 된다. 

먼저 18의 약수를 구하고 24의 약수를 구한다음 각 각 의 약수중에서 공통 약수를 추려낸 뒤 그중 제일 큰 수를 찾았다.

수의 크기가 작은 경우 빠르게 구할 수 있겠지만 만약 수가 큰 수라면 어떻게 될까?

각각 약수를 구한뒤 공약수를 구하고 최대 공약수를  구하는 과정은 굉장히 비효율적으로 보인다.

그럼 두 수의 최대공약수를 가장 효율적으로 구할 수 있는 방법이 무엇이 있을까?

유클리드 호제법을 통해서 두 수의 최대 공약수를 빠르게 구할 수 있다.

유클리드 호제 법으로 최대공약수 구하는 방식

여기서 기억할 공식은 큰 수 A를 작은수 B로 나누었을때 나누어 떨어진다면 최대공약수는 B가 된다.

1)  입력 받은 두 수중 큰 수를 A, 작은수를 B로 정한다.

2)  A 를 B 로 나눈값의 나머지를 R로 지칭한다.

3)  R 이 0이라면 A는 B로 나누어 지기 때문에 최대 공약수는 B가 된다.

4)  만약 R이 0이 아니라면 A값은 B로, B 값은 R로 변경한뒤 3번 과정을 반복한다. 

위의 유클리드 호제법을 자바 소스로 보면 다음과 같다.

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        long num1 = sc.nextLong();
        long num2 = sc.nextLong();
 
        // 큰수를 앞에 작은 수를 뒤에 위치시킨다.
        long gcd = getGCD(Math.max(num1, num2), Math.min(num1, num2));
        
        System.out.println(gcd);
    }
 
    public static long getGCD(long a, long b) {
        while(b > 0) {
            long tmp = a;
            a = b;
            b = tmp%b;
        }
        return a;
    }
}

최대 공약수를 구했으니 이제 최소 공배수를 알아보자.

최소공배수는 두개 이상의 수가 공통으로 가지는 배수 중 가장 작은 수를 말한다.

두 수 18과 24가 존재 할때 두 수의 배수는 다음과 같이 진행된다.

18의 배수 18, 36, 54, 72, 90 ...

24의 배수 24, 48, 72, 96 ...

두 수의 배수에서 같은 배수는 72로 나온다. 

최소 공배수를 구할때 두 수 A, B의 배수를 각각  구해가면서  A의 n번째 배수와 B의 m 번째 배수가 같으면 그 수가 최소 공배수가 되는 것이다.

하지만 1과 100000 의 최악의 예제를 받았을 경우

1의 배수를 100000 까지 구해야 최소공배수 100000을 구할 수 있다. 

이또한 굉장히 비효율 적인 방식이다.

최소 공배수를 구하는 가장 효율적인 방법은 위의 최대공약수를 구할때 사용한 유클리드 호제법을 이용하여 풀면 된다.

1) 두 수의 최대 공약수를 유클리드 호제법을 통하여 구한다.

2) 두 수 A, B를 곱한뒤 최대 공약수로 나눈 값을 최소 공배수로 출력한다.

위의 방법으로 최소 공배수를 구할 수 있다.

방금 정리한 최대 공약수와 최소 공배수를 구하는 방법으로 백준 2609 문제를 풀면 된다.

소스

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        long num1 = sc.nextLong();
        long num2 = sc.nextLong();
        
        long gcd = getGCD(Math.max(num1, num2), Math.min(num1, num2));
        long lcm = getLCM(num1, num2, gcd);
        
        System.out.println(gcd);
        System.out.println(lcm);
    }
 
    public static long getGCD(long a, long b) {
        while(b > 0) {
            long tmp = a;
            a = b;
            b = tmp%b;
        }
        return a;
    }
    
    public static long getLCM(long a, long b, long gcd) {
        return (a*b)/gcd;
    }
}