문제 링크: https://www.acmicpc.net/problem/2312

 

소인수분해를 하면 된다. 간단하다

// No. 2312
// 수 복원하기
// author: joe

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>

#include <algorithm>
#include <iostream>


using namespace std;

int histogram[100001];

int main() {

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t, n, n_tmp;
	int i, j;
	cin >> t;

	for (i = 0; i < t; ++i) {
		fill(histogram, histogram + 100001, 0);	//clear

		cin >> n;
		n_tmp = n;
		for (j = 2; j <= n_tmp; ++j) {
			while (n_tmp % j == 0) {
				n_tmp /= j;
				++histogram[j];
			}
		}

		for (j = 2; j <= n; ++j) {
			if (histogram[j]) {
				cout << j << ' ' << histogram[j] << endl;
			}
		}
	}

	
	return 0;
}