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

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

2312번: 수 복원하기

문제

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

---

간단한 소인수 분해 문제이다.

 

▶ Step #1 

소인수분해를 해야하기에 postInit() 메서드로 N범위 이내의 소수를 모두 구해준다.

빠르게 소수를 구하기 위해 에라토스테네스의 체 알고리즘을 사용해 구해준다.

 

▶ Step #2 

문제에서 요구하는 것은 주어진 수를 소인수분해를 하기 위해 사용했던 수와 그 수의 개수이다.

그러므로 개수를 세어주는 배열 하나와 어떠한 수를 사용했는지 기억하는 벡터 하나를 선언해준다.

 

▶ Step #3

2부터 진행해서 나눌 수 있는 소수일 경우 벡터에 그 수를 넣어주고 소인수분해를 진행한다. 진행하는 과정에서는 위에서 선언했던 배열에 개수까지 저장해준다.

 

입력으로 받았던 수가 0이 될 때까지 Step #3을 진행한다

 

▶ Step #4

벡터에 Step #3에서 소인수분해에 사용했던 수들이 담겨있기 때문에 문제 출력 요구에 맞춰 정렬을 진행한다.

그리고 개수를 세어주는 변수를 통해 소인수분해에 사용했던 개수까지 출력해준다.

 

#include <algorithm>
#include <iostream>
#include <vector>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using namespace std;

int prime[100000 + 1];
int counting[100000 + 1];

void postInit() {
	for (int i = 1; i <= 100000; i++) {
		prime[i] = i;
	}

	for (int i = 2; i <= 100000; i++) {
		for (int j = i + i; j <= 100000; j += i) {
			if (!prime[j]) continue;
			prime[j] = 0;
		}
	}
}

vector<int> solution(int x) {
	vector<int> chk;
	for (int i = 2; i <= 100000; i++) {
		if (!prime[i] || x % i != 0) continue;
		chk.push_back(i);
		while (1) {
			if (!x || x % i != 0) break;
			x /= i;
			counting[i]++;
		}
	}
	return chk;
}

void sortAndPrint(vector<int> &ps) {
	sort(ps.begin(), ps.end());
	for (auto& ptr : ps) {
		cout << ptr << " " << counting[ptr] << endl;
	}
}

void input() {
	int testCase;
	cin >> testCase;

	postInit();
	int number;
	while (testCase--) {
		cin >> number;

		memset(counting, 0, sizeof(counting));
		vector<int> chkNum = solution(number);
		sortAndPrint(chkNum);
	}
}


int main() {
	fastio;
	input();

	return 0;
}