Baekjoon 16563 어려운 소인수분해

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

소스결과 7612 KB / 1396 ms

출처 Baekjoon, Sogang Programming Contest

언어 C++ 17

분류 수학, 에라토스테네스의 체

 

설명

입력되는 n개의 수의 소인수들을 오름차순으로 출력한다.

 

소수를 구하는게 가장 큰 관건, 에라토스테네스의 체를 이용하여 소수 목록만 구하면 된다.

오름차순이기때문에, 2부터 시작해서 비교하면 된다.

 

알고리즘

1. 에라토스테네스의 체를 통해 1 ~ 100만 사이의 소수를 구한 후, 소수를 배열에 저장한다.

2. n개의 수를 입력 받는다.

3. 각 수를 가장 작은 소수로 나누고 나누어 떨어지면 그 수를 해당 소수로 나누고 소수를 출력한다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 5000000;
const int PRIME_MAX = 190000;

bool primeCheck[MAX + 1];
int primeList[PRIME_MAX];
int primeCount;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	for (int i = 2; i < (MAX / 2) + 1; i++)
	{
		if (!primeCheck[i])
		{
			primeList[primeCount++] = i;
			for (int j = 2; (j * i) < MAX; j++)
				primeCheck[j * i] = true;
		}
	}

	int tcc;

	cin >> tcc;

	while (tcc--)
	{
		int value;
		cin >> value;

		while (value > 1)
		{
			// Not Prime
			if (primeCheck[value])
			{
				for (int i = 0; i < primeCount; i++)
				{
					if (value % primeList[i] == 0)
					{
						cout << primeList[i] << ' ';
						value /= primeList[i];
						break;
					}
				}
			}
			// Prime
			else
			{
				cout << value;
				value = 1;
			}
		}

		cout << '\n';
	}
}