백준 2312번 C++

백준 2312번 수 복원하기

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

2312번: 수 복원하기

정답 코드

#include<iostream>
#include<math.h>
using namespace std;
int arr[100001] = { 1,1 };
int cou[100001];
void clear(int a) {
	for (int x = 2; x <= a; x++)
		arr[x] = 0;
}

void print(int a) {
	int count = 0;
	int m = a;
	for (int x = 2; x <= a; x++) {
		if (m % x == 0) {
			cou[x]++;
			m /= x;
			x--;
		}
	}
	for (int x = 2; x <= a; x++) {
		if (cou[x] != 0) {
			cout << x << " " << cou[x] << endl;
			cou[x] = 0;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
		for (int x = 2; x <= sqrt(100001); x++) {
			if (arr[x] != 0)
				continue;
			for (int y = x * x; y <= 100001; y += x) {
				arr[y] = 1;
			}
		}
	for (int x = 0; x < n; x++) {
		int a;
		cin >> a;
		print(a);
		clear(a);
	}
}

문제 풀이

얼핏 보면 단순히 계속 나누어서 구하면 될 것 같이 보이지만 그렇게 하면 시간초과가 발생합니다. 그래서 소수를  에라토스테네스의 체를 이용해서 구한 후 입력받은 수를 소수로 나눠줍니다.