취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17103번 문제인 골드바흐 파티션이다.
문제는 아래 링크를 확인하자.

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

100만을 넘는 소수는 주어지는 짝수의 합을 구성하는 소수로 쓰일 수 없으므로, 100만 이하의 모든 수에 대해 각 수가 소수인지 아닌지를 알 수 있는 에라토스테네스의 체를 구하자.

테스트케이스가 최대 100개로 적으므로, 각 테스트할 수 $x$에 대하여 합이 $x$가 되는 모든 $a\le b$인 양의 정수쌍 $a$와 $b$에 대하여 각각이 소수가 되는 경우가 몇 가지인지를 세어 문제를 해결하자. 각 테스트는 최대 50만가지 경우를 확인해보는 것으로 답을 구할 수 있으므로 이는 문제를 해결하기에 충분한 방법이다.

2를 제외한 소수는 모두 홀수이므로 4를 제외한 모든 짝수의 합을 구성하는 두 소수는 홀수임을 이용해 아래의 제출 코드와 같은 약간의 최적화를 할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int sieve[1000001];
int T;

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

	sieve[1] = 1;
	for (int i = 2; i < 1000; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 1000000; j += i) sieve[j] = 1;
	}

	cin >> T;
	while (T--) {
		int ans = 0;
		int x; cin >> x;

		for (int i = 3; i * 2 <= x; i += 2) {
			if (sieve[i] || sieve[x - i]) continue;
			ans++;
		}
		if (x == 4) ans = 1;

		cout << ans << '\n';
	}
}