[실전 문제] pfactorization

1. 문제

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

 

소인수란 소수인 인수(약수)를 의미한다.  

---

입력

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

출력

N의 소인수를 한 줄에 하나씩 오름차순으로 출력한다..

예제 입력

case 1) 72

case 2) 3

case 3) 6

case 4) 9991

예제 출력

case 1)

2
2
2
3
3

 

case 2)

3

 

case 3)

2

3

 

case 4)

97
103

 

 

 

2. 풀이

2부터 n까지 모든 수를 나눠보면서 나머지가 0일 경우 그 값을 출력하는 방식으로 진행하면 된다. 단, 1은 소수가 아니기 때문에 제외해야한다.

 

주어진 n의 범위를 고려하여, 반복문의 범위를 효율적으로 처리를 해주어야한다. '어떤 n이 두 개 이상의 인수으로 나타낼 수 있을 때, 인수 중 한개는 반드시 루트n 보다 작거나 같다'는 것을 이용하여 반복문의 범위를 루트n으로 처리해준다.

 

하지만 주의해야할 점이 있다. 예를 들어 n이 34일 경우,

• i = 2 일 때, (34 % 2 == 0) 조건을 만족하기에 while문 - 34 / 2 계산
• i = 2 일 때, (17 % 2 == 0) 조건을 불만족하기에 while문 종료
• i = 3 일 때, (17 % 3 == 0) 조건을 불만족하기에 while문 종료
• i = 4 일 때, (17 % 4 == 0) 조건을 불만족하기에 while문 종료
• i = 5 일 때, (17 % 5 == 0) 조건을 불만족하기에 while문 종료
• for문 종료

 

이와 같은 과정을 거치면서 17을 출력하지 못하는 경우가 발생한다. 따라서, 루트n으로 처리해주게 되면, 나뉘지 않은 값에 대한 출력을 못할 수 있기 때문에, 이에 대한 처리를 마지막에 해주어야한다.

import java.io.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());

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

        if(n != 1) bw.write(n + "");

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

}