백준 2312 자바 - 수 복원하기 (BOJ 2312 JAVA)

문제 : boj2312

 

 

  오랜만에 1분컷으로 푼 것 같다. 소인수분해의 결과는 결국 전부 소수가 될테니 미리 에라토스테네스의 체로 소수를 구해두고 수행하면 더 효율적이긴 하다. 하지만 N이 최대 100000이므로 2부터 N까지의 모든 수로 직접 나눠봐도 O(100000)밖에 안나온다. 따라서 그냥 brute force로 직접 나눠보면 쉽게 답을 구할 수 있다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (tc-->0) {
            int n = Integer.parseInt(br.readLine());
            for (int i = 2; i <= n; i++) {
                int cnt = 0;
                while (n%i==0) {
                    n/=i;
                    cnt++;
                }
                if (cnt != 0)
                    sb.append(i).append(' ').append(cnt).append('\n');
                if (n == 0)
                    break;
            }
        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}