[백준 #16563] 어려운 소인수분해(C++)

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

16563번: 어려운 소인수분해

#include <iostream>
#include <vector>
#include <algorithm> 

using namespace std;
int main()
{
	int N;
	cin >> N;
	vector<int>input(N);
	for (int i = 0; i < N; i++)
		cin >> input[i];
	int max = *max_element(input.begin(), input.end());

	vector<int>check(max + 1);
	for (int i = 2; i <= max; i++)
		check[i] = i;

	for (int i = 2; i * i <= max; i++)
	{
		if (check[i]==i)
		{
			for (int j = 2 * i; j <= max; j += i)
			{
				if (check[j]==j)
					check[j] = i;
			}
		}
	}

	for (int i = 0; i < N; i++)
	{
		int num = input[i];
		while (num!=1)
		{
			cout << check[num] << " ";
			num /= check[num];
		}
		cout << "\n";
	}

}

백준 #1929에서 사용했던 에라토스테네스의 체를 응용한다.

그 문제에서는 check 배열에 소수면 1, 소수가 아니면 0을 기록했다.

이번에는 먼저 자기 자신을 담아둔 뒤, 소수가 아니라면 그 수를 나눈 소수를 기록하는 것이다.

그렇다면 check 배열에는 소수라면 자기 자신, 소수가 아니라면 가장 작은 소인수가 기록된다.

 

입력된 자연수 중 max를 구해서 max까지 그 작업을 해주었다.

그다음, 출력을 하면 된다. 

 

num=45라면, check[45]=3(45의 가장 작은 소인수), 3 출력num=num/3=15check[15]=3, 출력num=num/3=5check[5]=5, 출력num=num/5=1이므로 while 문을 빠져나옴.