취미로 코딩하기

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

이번에 볼 문제는 백준 14905번 문제인 소수 4개의 합이다.
문제는 아래 링크를 확인하자.

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

모든 소수는 2 이상이므로 주어지는 수가 8보다 작다면 조건을 만족하는 네 수를 찾는 것은 항상 불가능함을 알 수 있다. 아래부터는 주어지는 수가 8 이상이라 가정하자.

prime gap $g_i$는 $i$번째 소수와 $i+1$번째 소수의 차를 나타내는 수열로, $i$번째 소수가 1억 이하일 경우 $g_i$의 최댓값은 47326693와 47326913의 차와 같은 220임이 잘 알려져있다. 따라서 1억 이하의 수가 주어질 때 이 수보다 작으면서 가장 큰 소수를 찾는 것은 많아야 220개의 수를 직접 소수판정하는 것으로 해낼 수 있다. 소수판정은 주어진 수의 제곱근 이하의 각 소수들로 나누어보는 것으로 해낼 수 있고 많은 수는 2나 3과 같은 작은 소수로 나누어떨어지므로, 소수들을 미리 에라토스테네스의 체 등으로 전처리해둔다면 이 과정은 충분히 빠르게 진행할 수 있다.

위 지식을 이용하면, 먼저 주어지는 수와 6 이상 차이가 나는 가장 큰 소수를 찾고 주어진 수에서 찾은 수를 뺀 수를 세 소수의 합으로 구성하는 것으로 문제를 해결할 수 있음을 알 수 있다. 한편, 골드바흐의 추측(Goldbach's Conjecture)이 충분히 작은 범위의 양의 정수에 대하여 성립함을 이용하면, 남은 수가 짝수가 되게끔 2 또는 3을 골라 뺀 다음 조건을 만족하는 남은 두 소수를 찾아 남은 문제를 해결할 수 있음을 관찰할 수 있다.

prime gap에 대한 자세한 내용은 링크를 참고하자.

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

#include <iostream>
#include <vector>
using namespace std;

bool sieve[10001];
vector<int> P;
void sieveinit() {
	sieve[0] = sieve[1] = 1;
	for (int i = 2; i < 10001; i++) {
		if (sieve[i]) continue;
		P.emplace_back(i);
		for (int j = i * i; j < 10001; j += i) sieve[j] = 1;
	}
}

int N;

void solve() {
	if (N < 8) {
		cout << "Impossible.\n";
		return;
	}
	for (int k = N - 6; k > 0; k--) {
		bool chk = 1;
		for (auto &p : P) {
			if (k % p) continue;
			if (k != p) chk = 0;
			break;
		}
		if (chk) {
			cout << k << ' ';
			N -= k;
			break;
		}
	}
	if (N & 1) N -= 3, cout << 3 << ' ';
	else N -= 2, cout << 2 << ' ';
	for (auto &p : P) {
		if (sieve[N - p]) continue;
		cout << p << ' ' << N - p << '\n';
		return;
	}
}

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

	sieveinit();
	while (cin >> N) solve();
}