[BOJ] 11653 소인수분해

문제

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

입력

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

출력

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

예제 입력 1

72

예제 출력 1

2
2
2
3
3

예제 입력 2

3

예제 출력 2

3

예제 입력 3

6

예제 출력 3

2
3

예제 입력 4

2

예제 출력 4

2

예제 입력 5

9991

예제 출력 5

97
103

---

풀이

처음에는 소인수분해기 때문에 나누는 수가 소수인지 확인하고 소수라면 나누어질 때까지 나누도록 했는데 시간초과됐다. 그래서 생각해보니 굳이 소수 여부를 확인하지 않아도 2부터 1씩 증가하면서 나누게 되면 자연스럽게 소수일 때만 나눠지게 되는 것을 알게 되었다. 그래서 소수를 따로 판별하지 않았다.

ex ) 나누는 수가 2로 나머지 없이 나누어지지 않을 때까지 나누면 나누는 수가 4가 되어도 이미 2로 다 나누었기 때문에 4로 나눌 수 없음. -> 자동적으로 소수만 나누어지게 된다.

1은 소수가 아니라 for문을 2부터 시작했고, 입력한 수가 소수일 경우 자신이 출력되어야 하기 때문에 n까지 돌렸다.

---

코드

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());
        int m = n;

        if (n == 1) {
            return;
        }

        for (int i = 2; i <= n; i++) {
            while (m % i == 0) {
                bw.write(i + "\n");
                m /= i;
            }
        }
        bw.flush();
    }
}