[백준 11653] 소인수 분해 (자바)

백준 11653번: 소인수 분해 (2트)

문제 설명

주어진 자연수를 소인수분해하여 각 인수를 출력하는 문제입니다. 소인수분해란 자연수를 소수들의 곱으로 나타내는 것을 의미합니다.

문제 접근 방법

1. 입력받은 수 N이 1보다 큰 동안 반복합니다.
2. 2부터 시작하여 N을 나누어 떨어뜨리는 가장 작은 소수를 찾습니다.
3. 해당 소수로 N을 나눈 후, 소수를 출력합니다.
4. 이 과정을 N이 1이 될 때까지 반복합니다.

시간 복잡도 분석

O(N)

• 최악의 경우, N이 소수인 경우에는 2부터 N까지의 모든 수를 나눠보아야 합니다.
• 따라서 시간 복잡도는 O(N)입니다. 하지만 일반적으로 소수는 N의 제곱근까지만 검사하면 되므로 평균적으로는 더 빠르게 동작합니다.

해결 방법

아래는 주어진 자연수를 소인수분해하여 출력하는 Java 코드입니다:

package re_02;

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

public class BOJ_11653_소인수_분해_2트 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        while (N > 1) {
            for (int i = 2; i <= N; i++) {
                if (N % i == 0) {
                    N = N / i;
                    System.out.println(i);
                    break;
                }
            }
        }
    }
}