[백준 자바] 2312번(수 복원하기) - 소인수분해

난이도 - 실버 3

문제

양의 정수 N이 주어졌을 때, 이 수를 소인수분해 한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다.

출력

각 테스트 케이스마다 각 인수와 그 인수가 곱해진 횟수를 한 줄씩 출력한다. 출력 순서는 인수가 증가하는 순으로 한다.

 

---

 

728x90

100000까지의 소수판별 배열을 생성한다(primes)

입력값을 하나씩 받아 가장 작은 소수부터 그 소수로 나누어 떨어지지 않을 때까지 나누기를 실행한다.

import java.io.*;

public class Main2312 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

    boolean[] primes = sieveOfEratosthenes(100000);

    StringBuilder sb = new StringBuilder();

    while (T-- > 0) {
      int N = Integer.parseInt(br.readLine());

      for (int i = 2; i <= N; i++)
        if (!primes[i]) {
          int count = 0;
          while (N % i == 0) {
            count++;
            N /= i;
          }
          if (count != 0)
            sb.append(i + " " + count + '\n');
        }
    }

    bw.write(sb.toString());

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

  static boolean[] sieveOfEratosthenes(int max) {
    boolean[] isPrime = new boolean[max + 1];

    for (int i = 2; i * i <= max; i++)
      if (!isPrime[i]) {
        for (int j = i * i; j <= max; j += i)
          isPrime[j] = true;
      }

    return isPrime;
  }
}