9020 : 골드바흐의 추측

사전에 미리 아리스토텔레스의 체를 활용하여 소수들을 담아두고 있는 테이블을 만들었다.

a + b = c일때

c랑 a를 알고 있으면 b를 알 수 있기 때문에(b = c - a) 이 방식으로 O(N^2)의 복잡도를 O(N)으로 줄였다.

#include <iostream>
#include <vector>

void PrimePartition( int& a,  int& b
	,  std::vector<bool>& primeTable,  int num)
{
	a = 0;
	b = 0;

	
	for (int i = 0; i < num; i++)
	{
		if (!primeTable[i])
			continue;

		int j = num - i;

		if (!primeTable[j])
			continue;

		if (a != 0 && b != 0
			&& abs(a - b) < abs(i - j))
			continue;

		a = (i >= j) ? j : i;
		b = (i >= j) ? i : j;

		if (abs(a - b) < 2)
			return;
	}
}

std::vector<bool> MakePrimeTable(const int maximum)
{
	std::vector<bool> primeTable(maximum + 1, true);

	primeTable[0] = false;
	primeTable[1] = false;

	for (size_t i = 2; i <= maximum; i++)
	{
		for (size_t j = 2; i * j <= maximum; j++)
		{
			primeTable[i * j] = false;
		}
	}

	return primeTable;
}

int main(void)
{
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	std::cin.sync_with_stdio(false);

	int N, maximum = 10000;
	std::vector<bool> primeTable = std::move(MakePrimeTable(maximum));


	std::cin >> N;

	

	for (size_t i = 0; i < N; i++)
	{
		int inputNum = 0;
		std::cin >> inputNum;
		int a = 0, b = 0;

		PrimePartition(a, b, primeTable, inputNum);

		std::cout << a << " " << b << "\n";

	}


	return 0;
}

9020번: 골드바흐의 추측 (acmicpc.net)

9020번: 골드바흐의 추측