[백준][C++] 2312: 수 복원하기

문제 링크: 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;
}

 

---

(2020. 01. 27 추가)

위 알고리즘은 되게 대충 짠 거고 효율적으로 하려면 n=2, 3, 5, 7, 9, ... , 2a+1 에 대해서만 검사를 하면 된다. 나중에 시간 남을 때 추가할 예정. 옛날 코드 보니까 창피하다..