🧩 Baekjoon 11653 - 소인수분해

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

예제

✅ 입력 1

72

✅ 출력 1

2
2
2
3
3

✅ 입력 2

3

✅ 출력 2

3

✅ 입력 3

9991

✅ 출력 3

97
103

작성 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Arrays;  
  
public class Main {  
    static int[] primeArr;  
    
    public static void main(String[] args) throws IOException {  
        // 1. 변수 선언 및 초기화  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int n = Integer.parseInt(br.readLine());  
        
        // 2. 처리 및 출력  
        makePrimeArr(n);  
        factorize(n);  
    }  
    
    static void makePrimeArr(int num) {  
        // 배열 초기화  
        primeArr = new int[num + 1];  
        Arrays.fill(primeArr, 1);  
        primeArr[0] = primeArr[1] = 0;  
        
        // 에라토스테네스의 체  
        for (int i = 2; i <= num; i++) {  
            if (primeArr[i] == 0) continue;  
            for (int j = i * 2; j <= num; j += i) primeArr[j] = 0;  
        }  
    }  
    
    static void factorize(int n) {  
        // 순회 처리  
        for (int i = 2; i <= n; i++) {  
            // 소수일 경우 가능할 때까지 나눗셈 처리  
            if (primeArr[i] == 1) {  
                while (n % i == 0) {  
                    System.out.println(i);  
                    n /= i;  
                }  
            }  
            
            // 종료 처리  
            if (n == 1) break;  
        }  
    }  
}

회고

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

public class Main {
    static int[] primeArr;
    
    public static void main(String[] args) throws IOException {
        // 1. 변수 선언 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        // 2. 처리 및 출력
        makePrimeArr(n);
        factorize(n);
    }
    
    static void makePrimeArr(int num) {
        // 배열 초기화
        primeArr = new int[num + 1];
        Arrays.fill(primeArr, 1);
        primeArr[0] = primeArr[1] = 0;
        
        // 에라토스테네스의 체
        for (int i = 2; i <= num; i++) {
            if (primeArr[i] == 0) continue;
            for (int j = i * 2; j <= num; j += i) primeArr[j] = 0;
        }
    }
    
    static void factorize(int n) {
        // 순회 처리
        for (int i = 2; i * i <= n; i++) {
            // 소수일 경우 가능할 때까지 나눗셈 처리
            if (primeArr[i] == 1) {
                while (n % i == 0) {
                    System.out.println(i);
                    n /= i;
                }
            }
        }
        
        // n이 1보다 크면 소수이므로 출력
        if (n > 1) {
            System.out.println(n);
        }
    }
}

• 위 코드처럼 제곱근까지만 처리해보기도 했는데 i * i 연산 때문인지 오히려 속도가 느려졌다.
• 그럼에도 입력 값이 큰 테스트 케이스가 많아진다면 제곱근까지만 처리하는 방식이 더 유리할 것으로 보인다.