2609 자바 ] 최대공약수와 최소공배수(풀이) / 유클리드 호제법

※ 문제

출처(https://www.acmicpc.net/problem/2609)

---

문제 이해하기.

두 수의 최대공약수와 최소공배수가 무엇인지 알아보자.

 

'예제 입력1'의 두 수 24와 18의 최대공약수는 6이다. 최대공약수는 두 수의 약수들 중 동일한 값중 제일 큰 값이다.

24의 약수는 [1, 2, 3, 4, 6, 8, 12, 24]이고 18의 약수는 [1, 2, 3, 6, 9, 18]이다. 겹치는 수 중에서 최대값은 6이다.

 

그리고 이 두 수의 최소공배수는 72이다. 최소공배수는 두 수의 배수들 중 동일한 값중 제일 작은 값이다.24의 배수는 [24, 48, 72, 96 ... ]이 있고 18의 배수는 [18, 36, 54, 72, ...] 이 있다. 겹치는 수 중에서 최소값은 72이다.

 

여기까지 이해했으면 어떻게 두 수의 최대공약수와 최소공배수를 구할 수 있는지 알아보자.

---

1. 성공

 1) 설계

두 수의 최대공약수를 구하기 위해 활용하기 좋은 효율적인 알고리즘이 있다.  그것은 '유클리드 호제법' 또는 '유클리드 알고리즘'이다.

 

유클리드 호제법은 간단하다. 두 수 A와 B가 있을 때 (A>B)가 성립하는 경우 A%B == 0이면 최대공약수는 B이다. 

하지만 A%B != 0 인 경우는 A는 B로 할당하고 B는 A%B로 할당해준 후 A%B가 0이될 때 까지 반복하는 것이다.

 

예를 들어 '예제 입력 1' 의 두 수 24와 18로 계산해보겠다.

 

최대공약수를 구했다면 이제 최소공배수를 구할 차례다. 최소공배수는 간단하다.

두 수의 곱 나누기 최대공약수를 하면 된다.

 

※ 결론 요약

 ① 최대공약수(GCF) : 유클리드 호제법

  - ex) (상단 이미지 참조)

 ② 최소공배수(GCM) : 두 수 곱한 후 나누기 최대공약수

  - ex) GCM = A*B / GCF

 

 2) 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int temp = 0;

        if(A < B) {
            temp = B;
            B = A;
            A = temp;
        }

        int GCF = 0;
        int GCM = A*B;
        while(true) {
            if(A % B == 0) {
                GCF = B;
                break;
            } else {
                temp = B;
                B = A % B;
                A = temp;
            }
        }
        GCM /= GCF;

        bw.write(GCF+"\n");
        bw.write(String.valueOf(GCM));

        bw.flush();
        bw.close();
    }
}

---

문제의 예제는 모두 통과하였으나 정확도의 이슈가 해결되지 않은 분은 아래 반례로 확인해보기 바랍니다.

※ 반례

입력 : 22 33

출력 : 11

          66

 

입력 : 1 4000

출력 : 1

          4000