백준 17103 - 골드바흐 파티션

골드바흐의 추측은 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다는 추측입니다.

수의 범위가 2 ~ 1,000,000 으로 크지 않아 에라토스테네스의 체를 이용해 이 범위의 소수를 모두 구해놓았습니다.

구해놓은 소수를 돌면서 입력받은 수에서 해당 소수를 뺀 수가 소수인지 체크해 두 소수로 만들어지는지 확인합니다.

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

bool* Eratos(int n);

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

	bool* primes = Eratos(1000001);
	std::vector<int> primeVec;

	for (int i = 2; i < 1000001; i++)
		if (primes[i])
			primeVec.push_back(i);

	int n;
	int* nums;

	std::cin >> n;
	nums = new int[n];

	for (int i = 0; i < n; i++)
		std::cin >> nums[i];

	for (int i = 0; i < n; i++)
	{
		int goldCnt = 0;

		for (auto it = primeVec.begin(); it != primeVec.end(); it++)
		{
			int second = nums[i] - *it;

			if (second < *it)
				break;

			if (std::binary_search(it, primeVec.end(), second))
				goldCnt++;
		}

		std::cout << goldCnt << "\n";
	}
	return 0;
}

bool* Eratos(int n)
{
	bool* primes = new bool[n];
	for (int i = 0; i < n; i++)
		primes[i] = true;

	primes[0] = false;
	primes[1] = false;

	for (int i = 2; i * i <= n; i++)
		if (primes[i])
			for (int j = i * i; j <= n; j += i)
				primes[j] = false;

	return primes;
}

이 코드보다 실행 속도가 훨씬 빠른 코드로 푸신 분이 있었는데, 이 코드는 아직 잘 이해가 되지 않아서 좀 더 봐바야겠습니다.. [블로그 링크]