취미로 코딩하기

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

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

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

골드바흐의 추측(Goldbach's conjecture)은 "모든 4 이상의 짝수는 두개의 소수의 합으로 나타낼 수 있다"는 추측이다. 이 때의 두 소수를 Goldbach pair이라 부른다. 골드바흐의 추측은 아직 증명되지는 않았지만 최소한 64비트 정수 자료형으로 나타낼 수 있는 짝수에 대해서는 항상 성립한다는 것은 계산을 통해 잘 알려져 있다.

위의 추측을 이용해 경우를 잘 나눠 문제를 해결해보자.

1) K=1인 경우

이 경우는 N이 소수인지를 판별하는 것으로 해결할 수 있다. 이는 sqrt(N)까지의 정수로 N을 직접 나눠보는 소수판별법을 이용하여 어렵지 않게 해결할 수 있다.

2) K=2인 경우

2-1) N<4인 경우

가장 작은 소수는 2이므로 두 소수의 합은 최소 4 이상이다. 따라서 이 경우 합이 N인 두 소수는 존재하지 않으므로 -1을 출력한다.

2-2) N>=4이고 N이 홀수인 경우

이 경우 더해서 N이 되는 두 정수는 짝수 하나와 홀수 하나로 구성되어있을 수밖에 없다. 짝수인 소수는 2뿐이므로 N-2가 소수이면 2와 N-2를, 아니라면 -1을 출력해 문제를 해결하자.

2-3) N=4인 경우

이 경우 2와 2를 출력해 문제를 해결하자.

2-4) N>4이고 N이 짝수인 경우

이 경우 더해서 N이 되는 두 소수는 모두 홀수여야 한다. 3부터 시작하여 홀수 p에 대해 p가 소수이면서 동시에 N-p 또한 소수가 되는 p를 하나 찾아내 p와 N-p를 출력하는 것으로 문제를 해결하자. 이는 반복문을 이용해 구현할 수 있다. 위키백과(링크)에 따르면 3,325,581,707,333,960,528보다 작은 짝수는 한 소수가 9781보다 작은 Goldbach pair을 무조건 가지고 있다는 점이 알려져있으므로 시간초과를 걱정할 필요는 없다.

3) K>2인 경우

3-1) N < K*2인 경우

가장 작은 소수는 2이므로 K개의 소수의 합은 최소 2*K 이상이다. 따라서 이 경우 합이 N인 K개의 소수는 존재하지 않으므로 -1을 출력한다.

3-2) N>=K*2이고 N이 짝수인 경우

K-2개의 2와 (N-(K-2)*2)의 Goldbach pair을 나열하면 합이 N인 K개의 소수를 얻어낼 수 있다. 이와 같은 Goldbach pair은 위의 2-3)과 2-4)와 같이 구할 수 있다.

3-3) N>=K*2이고 N이 홀수인 경우

1개의 3과 K-3개의 2와 (N-(K-3)*2)의 Goldbach pair을 나열하면 합이 N인 K개의 소수를 얻어낼 수 있다. 이와 같은 Goldbach pair은 위의 2-3)과 2-4)와 같이 구할 수 있다.

위의 내용을 잘 구현해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N, K;

void solve() {
	if (N < K * 2) {
		cout << -1;
		return;
	}
	if (N & 1) {
		N -= 3, K--;
		cout << 3 << ' ';
	}
	while (K > 2) {
		N -= 2, K--;
		cout << 2 << ' ';
	}
	if (N == 4) cout << 2 << ' ' << 2;
	else {
		int i = 3;
		while (1) {
			int j = N - i;
			bool chk = 1;
			for (int k = 3; k * k <= i; k += 2) {
				if (i % k == 0) {
					chk = 0;
					break;
				}
			}
			for (int k = 3; k * k <= j; k += 2) {
				if (j % k == 0) {
					chk = 0;
					break;
				}
			}

			if (chk) {
				cout << i << ' ' << j;
				return;
			}
			i += 2;
		}
	}
}

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

	cin >> N >> K;

	if (K == 1) {
		if (N == 1) {
			cout << -1;
			return 0;
		}
		bool chk = 1;
		for (int i = 2; i * i <= N; i++) {
			if (N % i == 0) chk = 0;
		}
		if (chk) cout << N;
		else cout << -1;
	}
	else if (K == 2) {
		if (N < 4) {
			cout << -1;
			return 0;
		}
		else if (N == 4) cout << 2 << ' ' << 2;
		else if (N & 1) {
			N -= 2;
			bool chk = 1;
			for (int i = 2; i * i <= N; i++) {
				if (N % i == 0) chk = 0;
			}
			if (chk) cout << 2 << ' ' << N;
			else cout << -1;
		}
		else {
			int i = 3;
			while (1) {
				int j = N - i;
				bool chk = 1;
				for (int k = 3; k * k <= i; k += 2) {
					if (i % k == 0) {
						chk = 0;
						break;
					}
				}
				for (int k = 3; k * k <= j; k += 2) {
					if (j % k == 0) {
						chk = 0;
						break;
					}
				}

				if (chk) {
					cout << i << ' ' << j;
					return 0;
				}
				i += 2;
			}
		}
	}
	else solve();
}