[백준] 16563 어려운 소인수 분해

백준 16563 어려운 소인수 분해

• https://www.acmicpc.net/problem/16563

⚡ 시간 초과

• 채점 7%에서 시간 초과가 나오는데 그 이유를 못찾겠다

#include <iostream>
#include <math.h>
using namespace std;

//7% 시간 초과 

int num[1000000] = { 0 };
int minFactor[5000000] = { 0 };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int n;
	cin >> n;

	int maxn = 0;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
		if (maxn < num[i]) maxn = num[i];
	}

	//에라토스테네스의 체 변형
	minFactor[0] = minFactor[1] = -1;
	for (int i = 2; i <= maxn; i++)
		minFactor[i] = i;

	int sqrtn = sqrt(maxn);
	for (int i = 2; i <= sqrtn; i++) {
		if (minFactor[i] == i)
			for (long long j = i * i; j <= maxn; j += i)
				if (minFactor[j] == j)
					minFactor[j] = i;
	}

	//소인수분해 출력
	int k;
	for(int i = 0; i<n; i++){
		k = num[i];
		while(k > 1) {
			cout << minFactor[k] << " ";
			k /= minFactor[k];
		}
		cout << endl;
	}
	return 0;
}

• 계속 고민했었는데 endl을 개행문자 "\n"로 바꾸니 통과되었다
  시간 초과 나올 때 C++ 입출력 시간부터 줄일 수 있는지 확인하자

• ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
• endl 대신 "\n"사용하기