[백준11653번] 소인수분해

문제

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

입력

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

출력

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

예제 입력 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

나의 풀이

처음에는 소수들을 미리 저장해놓고 그 소수들을 가지고 나눠야하나 생각을 했었다. 그래서 소인수분해 알고리즘에 대하여 검색을 해보니 그냥 i값을 2부터 증가시키면서 나누어 나머지가 0이 될때를 기록했다. 생각을 해보니 당연한것이었다. 왜냐하면 3인 소수로 나뉘지 않는다면 어차피 3의 배수들로도 나뉘지가 않으니말이다. 따라서 소수들을 따로 저장할 필요자체가 없었던 것이었다. 말로 설명하는 것보다 아래 코드를 보고 머리 속으로 생각을 해보면 쉽게 이해할 수 있을 것이다.

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * 11653번 소인수분해
 */
public class Baeckjun11653 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> result = new ArrayList<>();

          // 소인수분해 과정
        for (int i=2; i<=n; i++) {
              // i로 n이 나누어 떨어지면 몫을 n에 저장하고 while문을 돈다.
            while (n % i == 0) {
                n /= i;
                result.add(i);
            }
        }

          // 배열 출력 과정
        for (Integer i : result) {
            System.out.println(i);
        }
    }
}