[백준/BOJ] 2609번_최대공약수와 최소공배수 (C++/Java)

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

문제

---

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

입력

---

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

출력

---

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

💻 예제 입력

24 18

💻 예제 출력

6
72

풀이

---

Java는 반복문을 활용한 방법, C++은 유클리드 호제법을 활용한 방법으로 풀었다.

먼저 반복문으로 푸는 방법은, for 루프를 돌면서 i=1부터 a와 b를 모두 나누어 떨어지게 하는 수를 구한다. → 이 수가 최대공약수!

‘최대공약수 X 최소 공배수 = 두수의 곱’ 이므로 최소 공배수는 두수의 곱을 최대공약수로 나누어 구할 수 있다.

최대공약수는반복문이 아닌 유클리드 호제법으로도 구할 수 있다.

• 유클리드 호제법
  두 수의 최대공약수를 구하는 알고리즘
  ex) a = 48, b = 18

1. 큰 숫자를 작은 숫자로 mod연산을 한다.
   → 48 % 18 = 12
2. 작은 숫자를 1번에서 구한 나머지로 mod연산을 한다.
   → 18 % 12 = 6
3. 위 과정을 mod연산의 결과가 0이 나올때 까지 계속 반복한다. (작은 숫자를 앞선 연산의 결과값으로 mod 연산)
   → 18 % 6 = 0
4. 결과가 0이 되는 순간 나누는 수로 사용된 수가 두 수의 최대공약수가 된다.
   → 48, 18의 최대공약수는 6!

C++ 소스코드 (유클리드 호제법)

---

#include <iostream>
using namespace std;

int Euclid(int a, int b)
{
    int c = a % b;
    
    if (a > b) {
        while (c != 0) {
            a = b;      // 작은 수 담기
            b = c;      // 앞선 연산의 나머지 담기
            c = a % b;  // 큰 수를 작은 수로 mod 연산
        }
        return b;   // 마지막 mod 연산에 사용된 값 반환
    }
    else {
        while (c != 0) {
            b = a;
            a = c;
            c = b % a;
        }
        return a;
    }
}

int main(void)
{
    int a, b;
    cin >> a >> b;

    // 최대공약수 (유클리드 호제법)
    int max = Euclid(a, b);
    cout << max << "\n";
    
    // 최소공배수 (기존에 a * b 해놓은 값 나누기)
    int min = a * b / max;
    cout << min << "\n";
}

Java 소스코드 (반복문)

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int a = Integer.parseInt(s[0]);
        int b = Integer.parseInt(s[1]);
        int c = Math.min(a, b);  // a, b 중 더 작은 값 구하기

        // 최대공약수
        int max = 0;
        for (int i = 1; i <= c; i++) {
            if (a % i == 0 && b % i == 0)
                max = i;
        }
        System.out.println(max);

        // 최소공배수
        int min = a * b / max;
        System.out.println(min);
    }
}