백준 2609번 최대공약수와 최소공배수

문제 설명

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

두 개의 자연수 AAA와 BBB가 주어졌을 때 최대공약수(GCD)와 최소공배수(LCM)를 구하는 문제입니다.

---

입력

두 개의 자연수 AAA, BBB가 한 줄에 주어집니다. (1 ≤ A, B ≤ 10,000)

 

24 18

---

출력

첫째 줄에 두 수의 최대공약수, 둘째 줄에 두 수의 최소공배수를 출력합니다.

 

6
72

---

해결 방법

• 최대공약수는 유클리드 호제법을 사용하여 효율적으로 구할 수 있습니다.
• 최소공배수는 두 수의 곱을 최대공약수로 나누는 방식으로 계산합니다.

---

전체 코드

import java.util.Scanner;

public class Main {

    // 최대공약수(GCD)를 구하는 유클리드 호제법 함수
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

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

        System.out.println(gcdValue);
        System.out.println(lcmValue);
    }
}

---

코드 설명

• gcd(int a, int b): 유클리드 호제법을 이용해 최대공약수를 구합니다.
  • gcd(24, 18) → gcd(18, 6) → gcd(6, 0) → 6
• 최소공배수는 a * b / gcd(a, b) 공식을 활용합니다.

---

시간 복잡도

• 최대공약수: O(log(min(A, B))) → 유클리드 호제법 시간복잡도입니다.
  • 두 수 중 더 작은 수에 대해 로그만큼 반복합니다.
• 최소공배수 계산은 한 번의 곱셈과 나눗셈이므로 O(1)입니다.