Problem 17103

골드바흐 파티션

문제

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

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

문제 링크

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

예제 입력 1

5
6
8
10
12
100

예제 출력 1

1
1
2
1
6

solve

전체 범위의 소수들을 모두 구한다.(에라토스테네스의 체 이용)
이후 n - b = a 가 소수인 경우. 즉, 골드바흐의 추측을 만족하는 경우에 n = a + b 를 출력

위와 같이 골드바흐의 추측 문제와 같은 방식으로 접근하여 파티션의 개수만 출력한다.
- 이때 중복을 제거해야 하므로 count를 2로 나눈 몫을 출력하는데,
- 6 = 3 + 3, 10 = 5 + 5 와 같은 경우 중복이 발생하지 않는 한 쌍이 존재하므로
- 현재 입력받은 수 num을 기준으로 num / 2가 소수라면 count를 2로 나눈 몫에 1을 더하여 중복이 발생하지 않는 경우를 더해주어 출력하고
- 아니라면 count를 2로 나누어 중복을 제거 후 출력한다.

코드 설명

#include<iostream>

using namespace std;
const int MAX = 1000000;
int prime[MAX]; // 소수를 담을 배열
bool check[MAX + 1]; // 인덱스가 소수이면 false인 배열
int pn = 0; // 소수의 개수
int main(void)
{
	int n; // testcase
	cin >> n;
	check[1] = true; // 1은 소수가 아님

	for (int i = 2; i < MAX; i++) // 에라토스테네스의 체
	{
		if (check[i] == false) // 아직 (소수가 아니라고)판별되지 않았다면
		{
			prime[pn++] = i; // 소수이면 prime에 저장
			for (int j = i + i; j < MAX; j += i) // i*i로 하면 정수 범위를 벗어날 수 있음
			{
				check[j] = true; // 소수의 배수는 모두 제거
			}
		}
	}

	while (n--)
	{
		int num;
		cin >> num;

		int count = 0; // 파티션 수
		for (int i = 0; prime[i] < num; i++) // 소수가 현재 입력 수 보다 작은동안
		{
			if (!check[num - prime[i]]) // n - b = a(소수)라면
			{
				// cout << num << " = " << num - prime[i] << " + " << prime[i] << '\n';
				count++;
			}
		}
		if (!check[num / 2]) // num / 2 가 소수라면 - 즉, 6 = 3 + 3 과 같이 중복이 발생하지 않는 파티션이 존재하는 경우
			cout << count / 2 + 1 << '\n'; // 중복을 제거하고 1을 더함
		else
			cout << count / 2 << '\n'; // 중복 제거

	}
}

백준 17103번 골드바흐 파티션

Baekjoon algorithm