[백준 Java] 약수, 배수와 소수 - 11653번: 소인수분해

 

 

import java.io.*;

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

        for (int i = 2; i * i <= N; i++) { // O(√N) 반복
            while (N % i == 0) { // i로 계속 나눌 수 있을 때까지
                bw.write(i + "\n");
                N /= i;
            }
        }
        if (N > 1) { // 마지막 남은 값이 소수이면 출력
            bw.write(N + "\n");
        }

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