백준 16563번 (어려운 소인수분해) c++

문제

16563번: 어려운 소인수분해

단순히 백준 11653(소인수분해)문제와 비슷한줄 알고 바로 똑같이 코드를 작성해 주었습니다.

#include<iostream>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n;
	cin >> n;

	while (n--) {
		int k;
		cin >> k;
		for (int i = 2; i * i <= k; i++) {
			if (k % i)
				continue;
			while (k % i == 0) {
				cout << i<<' ';
				k /= i;
			}
		}
		if (k != 1)
			cout << k << '\n';
		else cout << '\n';
	}
	
	return 0;
}

하지만 70% 쯤에서 시간초과가 발생하였고 문제를 자세히 읽어보니 자연수의 개수(N)이 1000000개 

자연수 K 의 범위는 무려 2<=K<=50000000 이었습니다. 따라서 소인수분해를 하는 과정에서 시간초과가 날것이라고 생각했습니다.

---

그래서 생각한 방법이 에라토스테네스의 체를 이용해 5000000이하의 범위의 소수를 미리 구해 배열에 저장하여

그 배열에 있는 숫자로만 소인수분해를 하는 방법을 시도해봤습니다.

먼저 에라토스테네스의 체를 만들기 위해 배열의 인덱스 번호에 맞는 value값을 할당해 주었습니다.

int arr[5000001];
for (int i = 0; i < 5000001; i++) {
		arr[i] = i;
}

그 다음 벡터 v를 선언해 소수만 들어갈 공간을 만들어 주고 에라토스테네스의 체 방법으로 소수만 걸러내어 

벡터 v 에 저장해주었습니다.

vector<int>v; //소수만 저장할 공간
for (int i = 2; i < 5000001; i++) {
		if (arr[i] == 0)
			continue;
		v.push_back(i); //소수 저장
		for (int j = i+i; j < 5000001; j += i) {
			if (arr[j] == 0)
				continue;
			arr[j] = 0;
		}
	}

그 이후는 맨 처음 소인수분해 방식과 유사 합니다. v[i]는 무조건 소수이므로 소수로만 연산을 할 수 있게 되었습니다.

while (n--) {
		int k;
		cin >> k;
		for (int i =0; v[i]*v[i] <= k; i++) { 
			if (k % v[i])
				continue;
			while (k % v[i] == 0) {
				cout << v[i]<<' ';
				k /= v[i];
			}
		}
		if (k != 1)
			cout << k << '\n';
		else cout << '\n';
	}

 

 

---

전체 코드입니다.

#include<iostream>
#include<vector>
using namespace std;
vector<int>v;
int arr[5000001];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < 5000001; i++) {
		arr[i] = i;
	}
	
	for (int i = 2; i < 5000001; i++) {
		if (arr[i] == 0)
			continue;
		v.push_back(i);
		for (int j = i+i; j < 5000001; j += i) {
			if (arr[j] == 0)
				continue;
			arr[j] = 0;
		}
	}

	while (n--) {
		int k;
		cin >> k;
		for (int i =0; v[i]*v[i] <= k; i++) {
			if (k % v[i])
				continue;
			while (k % v[i] == 0) {
				cout << v[i]<<' ';
				k /= v[i];
			}
		}
		if (k != 1)
			cout << k << '\n';
		else cout << '\n';
	}
	
	return 0;
}