BOJ_2312 : 수 복원하기

👉 문제링크

2312번: 수 복원하기

---

---

🔸 문제 분석 🔸

• 양의 정수 N이 주어지면 소인수 분해 결과를 출력한다.
• 2부터 N까지 나누며, 몫이 1이 될 때까지 반복한다.
  • 나눈 수를 카운트한다
• 카운트한 나눈 수 들중에서 값이 1 이상인 것들만 출력한다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();

        StringBuilder sb = new StringBuilder();

        for (int t = 0; t < tc; t++) {
            int n = sc.nextInt();
            int[] arr = new int[n+1];
            int temp = n, pt = 2;

            while (temp > 1) {
                if (temp % pt == 0) {
                    arr[pt]++;
                    temp /= pt;
                }
                else {
                    pt++;
                }
            }

            for (int i = 2; i < n+1; i++) {
                if (arr[i] > 0) {
                    sb.append(i + " " + arr[i] + "\n");
                }
            }
        }
        sb.deleteCharAt(sb.length()-1);
        System.out.print(sb);
    }
}

🔸 코드 해석 🔸

• temp의 초기값으로 n을 저장한다.
• temp가 1이 될 때까지 계산을 반복한다.
  • temp를 pt로 나눠 0이되면 arr[pt]의 값을 1 증가시킨다.
    • temp값을 pt로 나눈 몫으로 변경한다.
  • 나눠서 0이 되지 않으면 pt를 +1 시킨다.
• arr 중에 값이 1 이상인 경우만 출력한다.

---

🔸 end 🔸

• 간단히 풀었던 것 같은데, 에라토스테네스의 체로도 풀 수 있는 것 같다.