[백준/C++] 17103번 : 골드바흐 파티션 (소수 문제)

골드바흐 파티션 

문제

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

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

입력

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

출력

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

예제 입력 1

5
6
8
10
12
100

예제 출력 1

1
1
2
1
6

---

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

const int Max = 1000001;
bool check[Max];


int GetPartition(int n)
{
	int cnt = 0;
	for(int i = 0; i <= n/2; i++)
	{
		if (!check[i] && !check[n - i])
			cnt++;
	}
	return cnt;
}

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

	check[0] = check[1] = true;
	for(int i = 2; i <= sqrt(Max); i++)
	{
		if(!check[i])
		{
			for (int j = i + i; j <= Max; j += i)
				check[j] = true;
		}
	}

	int T;
	cin >> T;
	for(int t = 0; t < T; t++)
	{
		int N;
		cin >> N;

		cout << GetPartition(N) << '\n';
	}

	return 0;
}

 

해당 문제는 제한시간이 0.5초로 매우 작다.

따라서 파티션의 개수를 구하기위해 2부터 n까지의 for문을 모두 돌면 시간 초과가 걸리게 된다.

 

우선, 에라토스테네스의 채를 이용해 소수를 판별하는 bool 배열을 초기화하였고, 두 소수의 합을 구하기 위해 check[i] 와 check[n-i]를 구하였다.

 

처음에는 두 소수의 합을 구하려고 2중 for문을 돌렸는데, 사실 두 소수의 합이 n이 나오려면, 그냥 i와 n-i 를 구하면 되는거였다..!

 

그리고, 두 소수의 순서만 다른 것은 같은 파티션으로 판단하기 때문에 for문을 n번까지 전부 돌리지 않고, 0부터 n/2 번까지만 절반만 돌렸다. 

 

그럼 자연스럽게 중복처리도 없어지고 연산 시간도 줄일 수 있다.

---

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

17103번: 골드바흐 파티션