[백준] 11653

소인수 분해

소수 판별 & 약수에서 확장한 사고이다.
제곱근을 기준으로 절반만 살펴보아도, 약수 원리로 인해 소인수 분해가 가능하다.
제곱근 기준으로 절반만 살펴보되, 같은 수에 대해서 더이상 인수분해가 되지 않을 때까지 반복해서 계산한다.
! 특히 주의!
모든 계산을 끝내고 마지막에 남은 수가 1보다 크다면, 그것은 제곱근 기준 이하 절반에 해당하지 않는 큰 소수인 경우이다.
해당 숫자를 빼지 않도록 조심해야 한다.

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        for(int i=2; i*i<=N;i++) {
            while(left%i == 0) { // i로 더이상 안 나누어질 때까지
                bw.write(i+"\n");
                left = left/i;
            }
        }
        if(left > 1) bw.write(left+"\n"); // 마지막에 나누고 더이상 안 나누어지는 소수
        bw.flush();
        bw.close();
        br.close();
    }
}