lango

찍먹? 부먹?
난 부먹 개발자.

1 minute read



입출력 예시

Input-1
72
Output-1
2
2
2
3
3

Input-2
9991
Output-2
97
103


문제 풀이

문제를 풀기 앞서 소인수분해가 뭔지 알아보자.

소인수분해란?
1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는 방법을 말한다.
쉽게 말하자면 소수들의 곱으로 어떠한 수를 표현하는 것이다.

1
2
3

4 = 2*2(2의2승)
48 = 2*2*2*2*3(2의4승 * 3)
72 = 2*2*2*3*3(2의3승 * 3의2승)

그렇다면 N을 가지고 어떻게 소인수분해를 할 수 있을까?

  • 2부터 N까지 반복하며 N이 나눠지는 지를 확인한다.
  • N이 소수로 나눠진다면 N을 소수로 나눈다.

위 과정을 반복하여 N이 1이 된다면 소인수분해가 끝난 것으로 생각하면 된다. 문제 요구사항대로 소수들의 곱을 출력해야 하기에 N이 소수로 나눠질때 소수를 출력하자.


그렇다면 소인수분해 과정을 코드로 작성해보자.

1
2
3
4
5
6
7
8

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

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

N을 입력받고, 2부터 N까지 반복하는 반복문 안에서 N이 i로 나눠진다면 i를 출력하고, N을 i로 나누고 i보다 작은 1이 될때까지 반복하게 된다.



작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import java.io.*;

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<=N; i++) {
            while(N%i == 0) {
                bw.write(i + "\n");
                N /= i;
            }
        }

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

회고

  • 소인수 분해를 코드로 표현하며, 특정 수를 소수들의 곱으로 나타낼 수 있었다.

You may also enjoy