[11653] 소인수분해

난이도: ★★☆☆☆ • solved on: 2025-07-18

---

문제 요약

• 문제 유형: 정수론, 소인수분해
• 요구사항: 자연수 N(2 ≤ N ≤ 10,000,000)을 소인수분해하여 오름차순으로 한 줄에 하나씩 출력해야 한다.

---

사용 개념

1. 자료구조

   • 없음 (정수 변수와 출력 버퍼만 사용)

2. 알고리즘/기법

   • Trial Division (나눗셈 테스트)
   • Prime Factorization (소인수분해)

3. 핵심 키워드

   • 소수(prime number), 제곱근(square root), 시간 복잡도(time complexity)

---

풀이 아이디어 및 코드

방법 1 : 2부터 N까지 순차적으로 나누기

1. 문제 분해
   • i = 2부터 N까지 1씩 증가시키며 N이 i로 나누어떨어지면 출력 후 N /= i.
   • 한 인수를 모두 나눴으면 i를 1로 초기화하여 다음 턴에 2부터 다시 검사.
2. 핵심 로직 흐름

   for i = 2 … N:
       if N == 1: break
       if N % i == 0:
           print i
           N /= i
           i = 1               // 재시작

3. 예외 처리
   • N이 1 또는 2인 경우 바로 출력 후 종료

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        for(int i = 2; i <= n; i++){
            if(n == 1 || n == 2){
                sb.append(i);
                break;
            }
            if(n % i == 0){
                sb.append(i);
                sb.append("\n");
                n = n / i;
                i = 1;
                continue;
            }
            if(n==i){
                sb.append(i);
                sb.append("\n");
            }
        }
        System.out.print(sb.toString());
    }
}

---

방법 2 : √N까지만 검사 후 잔여 인수 처리

1. 문제 분해

• 2 ≤ i ≤ √N 범위만 순회해도 충분하다.
• 각 i마다 while (n % i == 0)로 완전히 나눈다.
• 반복이 끝난 뒤 n > 1이면 남은 n은 소수이므로 마지막 인수로 출력.

2. 핵심 로직 흐름

   for i = 2 … while i*i <= n:
       while n % i == 0:
           print i
           n /= i
   if n > 1: print n

3. 예외 처리
   • N이 1이면 출력 없이 종료.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        long n = Long.parseLong(br.readLine());   // n은 10,000,000 이하

        for (long i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                sb.append(i).append('\n');
                n /= i;
            }
        }
        if (n > 1) sb.append(n).append('\n');     // 잔여 인수
        System.out.print(sb);
    }
}

---

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N) (케이스 N이 소수일 때 비효율적)
• 공간 복잡도: O(1)

방법 2

• 시간 복잡도: O(√N)
  (소수인 경우에도 √N까지만 검사)
• 공간 복잡도: O(1)

---

어려웠던 점

• 방법 1에서는 i를 1로 리셋하는 트릭이 직관적이지 않아 로직이 길어졌다.
• N이 소수인 경우 전체 범위를 순회하므로 비효율적이었다.

---

배운 점 및 팁

• 소인수분해에서 √N까지만 검사한 뒤 남은 수가 1보다 크면 그것이 마지막 소수 인수다.
• while (n % i == 0) 형태로 중복 인수를 한꺼번에 제거하면 코드가 간결해진다.

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/11653
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천) :
  • [1676] 팩토리얼 0의 개수
  • [1747] 소수&팰린드롬
• 확장 문제 (GPT 추천) :
  • [1929] 소수 구하기