백준 11653번: 소인수분해

주어진 정수 N을 소인수분해하여 그 결과를 오름차순으로 출력하는 문제입니다. 정수론의 기본 개념인 소인수분해를 구현하는 가장 대표적인 문제로, 시험 분할법(Trial Division)과 제곱근 최적화를 이해하는 것이 핵심입니다.

---

✅ 문제 개요

항목	내용
문제 번호	11653번 - 소인수분해
난이도	실버 5
핵심 알고리즘	수학, 정수론, 소수 판정

---

✅ 문제 설명 요약

• 입력: 첫째 줄에 정수 N이 주어집니다. (1 ≤ N ≤ 10,000,000)
• 출력: N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력합니다.
• 규칙:
  • N이 1인 경우에는 아무것도 출력하지 않습니다.
  • 소인수는 소수(prime number)인 인수(factor)를 의미합니다.

---

✅ 풀이 전략

소인수분해는 주어진 수를 소수들의 곱으로 나타내는 것입니다. 가장 기본적인 방법은 가장 작은 소수부터 차례대로 나누어보는 시험 분할법(Trial Division)을 사용하는 것입니다.

1️⃣ 핵심 원리: 시험 분할법 (Trial Division)

• 가장 작은 소수인 2부터 시작하여, 주어진 수 N을 나누어 봅니다.
• 만약 N이 2로 나누어떨어진다면, 2는 N의 소인수입니다. 2를 출력하고, N을 2로 나눈 몫으로 업데이트합니다.
• 이 과정을 N이 더 이상 2로 나누어떨어지지 않을 때까지 반복합니다.
• 그다음 소수인 3으로 위 과정을 반복하고, 그다음 소수인 5로 반복... 하는 식으로 진행합니다.

2️⃣ 성능 최적화: √N까지만 확인하기

• 모든 수를 다 확인할 필요는 없습니다. 어떤 수 N의 약수는 그 제곱근(√N)을 기준으로 대칭적으로 존재합니다.
• 따라서, N을 나누는 소수는 √N보다 작거나 같은 수만 확인하면 충분합니다.
• 만약 √N까지 확인했는데도 N이 1이 아니라면, 남은 N은 그 자체가 √N보다 큰 소수라는 의미입니다.
• 코드로 구현할 때는 i <= Math.sqrt(N) 보다 i * i <= N 조건이 부동소수점 연산이 없어 더 효율적입니다.

3️⃣ 알고리즘 설계

1. N을 입력받고, N이 1이면 즉시 종료합니다.
2. for 반복문을 i = 2부터 i * i <= N까지 실행합니다.
3. 안쪽에 while 반복문을 두어, N % i == 0 (즉, N이 i로 나누어떨어지는 동안) 다음을 반복합니다.
   • i를 출력합니다.
   • N을 N / i로 업데이트합니다.
4. 바깥쪽 for 반복문이 모두 끝난 후, 만약 N이 1보다 크다면, 그 남은 N 자체가 마지막 소인수이므로 N을 출력합니다.

예시: N = 90
1. i = 2: 90 % 2 == 0. 2 출력. N = 45.
2. i = 2: 45 % 2 != 0. while문 종료.
3. i = 3: 45 % 3 == 0. 3 출력. N = 15.
4. i = 3: 15 % 3 == 0. 3 출력. N = 5.
5. i = 3: 5 % 3 != 0. while문 종료.
6. i = 4: 16 > 5 (i*i > N), for문 종료.
7. for문 종료 후 N은 5 (1보다 큼). 5 출력.
8. 최종 결과: 2, 3, 3, 5

---

✅ Java 코드 예제

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

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));

        int N = Integer.parseInt(br.readLine());

        // N이 1인 경우는 아무것도 출력하지 않음
        if (N == 1) {
            bw.flush();
            bw.close();
            br.close();
            return;
        }

        // 1. i*i <= N 까지만 확인
        for (int i = 2; i * i <= N; i++) {
            // 2. i로 나누어 떨어지는 동안 반복
            while (N % i == 0) {
                bw.write(i + "\n");
                N /= i;
            }
        }

        // 3. 루프 종료 후 N이 1보다 크면, 남은 N은 소인수
        if (N > 1) {
            bw.write(String.valueOf(N));
        }

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

---

⚠️ 실전 주의사항

항목	설명
N=1 처리	문제 조건에서 N=1일 경우 아무것도 출력하지 말라고 명시했으므로, 이 경우를 가장 먼저 처리하고 프로그램을 종료하는 것이 깔끔합니다.
반복문 조건 최적화	for (int i = 2; i <= N; i++) 로직도 정답은 맞지만, N이 클 경우 매우 비효율적입니다. i * i <= N으로 최적화하는 것이 핵심입니다.
마지막 소인수	for문이 끝난 후 N이 1보다 크면, 그 남은 N 자체가 소인수임을 잊고 출력하지 않는 실수를 하기 쉽습니다. 이 부분을 반드시 처리해야 합니다.
출력 형식	각 소인수를 한 줄에 하나씩 출력해야 하므로, bw.write(i + "\n") 또는 bw.newLine()을 사용해야 합니다.

---

📝 마무리 요약

✔️ 소인수분해의 기본은 2부터 시작하여 N을 나누어보는 것입니다.
✔️ 나누어떨어지면, 그 수로 더 이상 나누어지지 않을 때까지 계속 나누면서 몫을 갱신하고 나눈 수를 출력합니다.
✔️ 성능을 위해 나누는 수는 √N까지만 확인하면 됩니다. (코드는 i * i <= N으로 구현)
✔️ 루프 종료 후 N이 1보다 크면, 그 남은 수도 소인수이므로 반드시 출력해야 합니다.