J_Primes Problem

• 2015 acm-icpc 예선
• Problem J 3-Primes Problem

using namespace std;

vector primes;
void init()
{
	for (int i = 2; i < 1000; i++)
	{
		int j = 0, length = primes.size();
		for (; j < length; j++)
		{
			if (i % primes[j] == 0)
				break;
		}
		if (j == length)
			primes.push_back(i);
	}
}

bool findisPrime(int Value)
{
	for (int i = 0; i < primes.size(); i++)
	if (primes[i] > Value)
		return false;
	else if (primes[i] == Value)
		return true;

	return false;
}
int main()
{
	init();
	int T;
	for (scanf("%d", &T); T--;)
	{
		int K;
		scanf("%d", &K);

		int length = primes.size();
		vector R;
		bool bp = false;
		for (int i = 0; i < length; i++)
		{
			int _R1 = primes[i];
			for (int j = 0; j < length; j++)
			{
				int _R2 = primes[j];
				int _R3 = K - _R1 - _R2;
				if (_R2 > K)
					break;
				else if (findisPrime(_R3))
				{
					R.push_back(_R1);
					R.push_back(_R2);
					R.push_back(_R3);
					bp = true;
					break;
				}
			}
			if (bp || (_R1 > K))
				break;
		}
		if (bp)
		{
			sort(R.begin(), R.end());
			for (int i = 0; i < R.size(); i++)
				printf("%d%c", R[i], (i == R.size() - 1) ? '\n' : ' ');
		}
		else
			printf("0\n");
	}
	return 0;
}