플리나를 위하여

#include <iostream>
using namespace std;

void BAEKJOON_9020()
{
	bool primeArr[10001] = { false };
	for (int j = 4; j <= 10000; j += 2)
	{
		primeArr[j] = true;
	}
	for (int i = 3; i <= 10000; i += 2)
	{
		for (int j = i * 3; j <= 10000; j += i * 2)
		{
			primeArr[j] = true;
		}
	}

	int T;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		int n;
		cin >> n;
		if (n == 4)
		{
			cout << 2 << ' ' << 2 << endl;
		}
		else
		{
			int currentNumber = (n / 2) % 2 != 0 ? n / 2 : n / 2 - 1;
			while (currentNumber > 0)
			{
				if (!primeArr[currentNumber] && !primeArr[n - currentNumber])
				{
					cout << currentNumber << ' ' << n - currentNumber << endl;
					break;
				}
				currentNumber -= 2;
			}
		}
	}
	return;
}

#include <iostream>
using namespace std;
// 각 수마다 소수인지 확인하는 방식
void BAEKJOON_4948()
{
	int n;
	while (cin >> n && n != 0)
	{
		int countPrime = 0;
		for (int i = n + 1; i <= n * 2; i++)
		{
			bool isPrime = true;
			if (i > 2 && i % 2 == 0)
			{
				isPrime = false;
			}
			else
			{
				for (int j = 3; j * j <= i; j += 2)
				{
					if (i % j == 0)
					{
						isPrime = false;
						break;
					}
				}
			}
			if (isPrime)
			{
				countPrime++;
			}
		}
		cout << countPrime << endl;
	}
	return;
}

// 에라토스테네스의 체를 이용한 방식
void BAEKJOON_4948()
{
	int n;
	bool primeArr[246913] = { false };
	for (int j = 4; j <= 246912; j += 2)
	{
		primeArr[j] = true;
	}
	for (int i = 3; i <= 246912; i += 2)
	{
		for (int j = i * 3; j <= 246912; j += i * 2)
		{
			primeArr[j] = true;
		}
	}

	while (cin >> n && n != 0)
	{
		int countPrime = 0;
		for (int i = n + 1; i <= n * 2; i++)
		{
			if (!primeArr[i])
			{
				countPrime++;
			}
		}
		cout << countPrime << endl;
	}
	return;
}

#include <iostream>
using namespace std;

void BAEKJOON_1929()
{
	// 소수는 false, 합성수는 true
	bool primeArr[1000001] = { false };
	for (int j = 4; j <= 1000000; j += 2)
	{
		primeArr[j] = true;
	}
	for (int i = 3; i <= 1000000; i += 2)
	{
		for (int j = i * 2; j <= 1000000; j += i)
		{
			if (!primeArr[i])
			{
				primeArr[j] = true;
			}
		}
	}
	
	int M;
	int N;
	cin >> M >> N;
	M = M < 2 ? 2 : M;
	for (int i = M; i <= N; i++)
	{
		if (!primeArr[i])
		{
			cout << i << "\n";
		}
	}
	return;
}

#include <iostream>
using namespace std;

void BAEKJOON_2581()
{
	int M;
	int N;
	cin >> M >> N;
	M = M > 1 ? M : 2;

	int sumPrime = 0;
	int minPrime = 0;

	for(int i = M; i <= N; i++)
	{
		bool isPrime = true;
		for (int j = 2; j * j <= i; j++)
		{
			if (i % j == 0)
			{
				isPrime = false;
				break;
			}
		}
		if (isPrime)
		{
			sumPrime += i;
			if (!minPrime)
			{
				minPrime = i;
			}
		}
	}

	if (sumPrime)
	{
		cout << sumPrime << endl;
		cout << minPrime << endl;
	}
	else
	{
		cout << "-1" << endl;
	}

	return;
}

#include <iostream>
using namespace std;

void BAEKJOON_1978()
{
	int N;
	cin >> N;
	int count = 0;

	for (int i = 0; i < N; i++)
	{
		int number;
		cin >> number;
		bool primeCheck = number >= 2 ? true : false;
		for (int j = 2; j * j <= number; j++)
		{
			if (number % j == 0)
			{
				primeCheck = false;
				break;
			}
		}
		if (primeCheck)
		{
			count++;
		}
	}
	cout << count << endl;
	return;
}

#include <iostream>
using namespace std;

int getGcd(int a, int b)
{
	while (b != 0)
	{
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int getLcm(int a, int b)
{
	return a * b / getGcd(a, b);
}

void BAEKJOON_6064()
{
	int T;
	cin >> T;

	int M;
	int N;
	int x;
	int y;

	while(T--)
	{
		cin >> M >> N >> x >> y;
		int result = -1;
		int endDate = getLcm(M, N);
		for (int i = 0; x + M * i <= endDate; i++)
		{
			if ((x + M * i) % N == y % N)
			{
				result = M * i + x;
				break;
			}
		}
		cout << result << endl;
	}
	return;
}

#include <iostream>
using namespace std;

void BAEKJOON_2775()
{
	int T;
	cin >> T;
	int apt[15][15] = { 0 };
	for (int i = 1; i <= 14; i++)
	{
		apt[0][i] = i;
	}
	for (int i = 1; i <= 14; i++)
	{
		for (int j = 1; j <= 14; j++)
		{
			for (int n = 1; n <= j; n++)
			{
				apt[i][j] += apt[i - 1][n];
			}
		}
	}

	for (int i = 0; i < T; i++)
	{
		int k;
		int n;
		cin >> k >> n;
		cout << apt[k][n] << endl;
	}
	return;
}

#include <iostream>
using namespace std;

void BAEKJOON_10250()
{
	int T;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		int H;
		int W;
		int N;
		cin >> H >> W >> N;
		int roomNumber = (N % H == 0 ? H : N % H) * 100;
		roomNumber += (N % H == 0 ? N / H : N / H + 1);
		cout << roomNumber << endl;
	}
	return;
}