[백준] 11653번 : 소인수분해 (JAVA)

🔗 문제 링크

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

---

📌 문제 개요

자연수 N이 주어졌을 때, N을 소인수분해하여
소인수를 오름차순으로 한 줄에 하나씩 출력하는 문제

---

📌 접근 방법

• 2부터 시작하여 N이 나누어지는지 검사
• 나누어지면 출력 후 계속 나눔
• 더 이상 나누어지지 않으면 다음 수로 증가
• 반복은 i * i <= N까지만 수행
• 반복 후 N > 1이면 마지막 소수 출력

---

📌 핵심 아이디어

왜 while을 사용하는가?

• 소인수는 중복될 수 있다.

예시: 12 = 2 × 2 × 3

2가 두 번 등장하므로 한 번만 나누면 안 된다.

---

📌 왜 i * i <= N까지만 검사하는가?

어떤 수 N이 두 수의 곱이라면
그 중 하나는 반드시 √N 이하이기 때문이다.

따라서 √N까지만 검사해도 모든 소인수를 찾을 수 있다.

---

📌 전체 코드

package no_11653;

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

public class No11653 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for(int i = 2; i * i <= n; i++){
            while (n % i == 0){
                System.out.println(i);
                n /= i;
            }
        }

        if (n > 1) {
            System.out.println(n);
        }
    }
}

---

📌정리

• 소인수는 중복될 수 있으므로 while 사용
• √N까지만 검사하면 시간복잡도 O(√N)
• 마지막에 남은 값 처리 필수