[BOJ] 백준 2312 수 복원하기

[문제]

https://www.acmicpc.net/problem/2312

 

[소스 코드]

import java.io.*;
import java.util.*;
public class Main {
	static boolean[] prime = new boolean[100001];
	static List<Integer> list = new ArrayList<>();
	public static void main(String[] args) throws IOException {
		isPrime();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while(t-->0) {
			int n = Integer.parseInt(br.readLine());
			for(int i : list) {
				int cnt = 0;
				while(n%i==0) {
					cnt++;
					n /= i;
				}
				if(cnt!=0) {
					System.out.println(i+" "+cnt);
				}
			}
		}
	}
	private static void isPrime() {
		Arrays.fill(prime, true);
		prime[1] = false;
		for(int i=2;i*i<=100000;i++) {
			if(!prime[i]) continue;
			for(int j=i*i;j<=100000;j+=i) {
				prime[j] = false;
			}
		}
		for(int i=2;i<=100000;i++) {
			if(prime[i]) list.add(i);
		}
	}
}