Baekjoon 17103 골드바흐 파티션

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

소스결과 3276 KB / 12 ms

출처 Baekjoon

언어 C++17

분류 수학, 정수론

 

설명

골드바흐의 추측 : 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 를 만족하는 경우의 수를 출력해주자.

 

소수를 구하기 위한 에라토스테네스의 체를 이용하면 된다. 

두 소수가 같아도 된다.

 

알고리즘

1. 에라토스테네스의 체를 이용하여 소수를 구한 후 저장한다.

2. TC의 개수와 TC를 입력받는다.

3. 각각의 TC에 대하여 가장 작은 소수 부터 반복을 진행한다.

 3 - 1. TC의 값에서 소수를 뺸 값이 소수라면 결과값을 1 증가시킨다.

 3 - 2. 현재 소수의 값이 TC보다 커질 때 까지 반복한다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 1000000;
const int PRIMEMAX = 79498;

bool isPrime[MAX + 1];
int primeList[PRIMEMAX];
int primeCount;

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

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

	int tcc;
	cin >> tcc;

	while (tcc--)
	{
		int tar;
		int res = 0;

		cin >> tar;

		for (int i = 0; primeList[i] < tar; i++)
			if (tar - primeList[i] >= primeList[i] && !isPrime[tar - primeList[i]])
				res++;

		cout << res << '\n';
	}

	return 0;
}