[C++] 백준/Silver/6588. 골드바흐의 추측

문제: 골드바흐의 추측 (백준 6588번)

문제 분석

골드바흐의 추측은 "4 이상인 모든 짝수는 두 개의 소수의 합으로 나타낼 수 있다" 는 정수론의 가설이다.
이 문제에서는 n이 주어졌을 때, 두 소수의 합으로 표현하는 방법을 찾아 출력하는 것이 목표이다.

---

1. 에라토스테네스의 체를 이용한 소수 판별
   • 100만까지의 숫자에서 소수를 빠르게 판별하기 위해 에라토스테네스의 체를 사용한다.
   • prime[i]가 true이면 소수, false이면 합성수로 설정한다.
2. 두 포인터를 활용한 탐색
   • left는 2부터 시작하고, right는 n부터 시작한다.
   • 두 포인터가 가리키는 값이 소수인지 확인하면서,
     • 합이 n보다 크다면 right를 줄인다.
     • 합이 n보다 작다면 left를 증가시킨다.
   • 합이 n이 되는 순간 두 수를 출력한다.

전체 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<bool> prime(1000000, true);
	for (int i = 2; i < 1000; i++) {
		if (!prime[i])continue;
		for (int j = i + i; j < 1000000; j += i) {
			prime[j] = false;
		}
	}
	while (n) {
		int left = 2, right = n;
		cout << n << " = ";
		while ((left + right) != n) {
			if (left + right > n)
			{
				do { right--; } while (!prime[right]);
			}
			else if (left + right < n)
			{
				do { left++; } while (!prime[left]);
			}
		}
		cout << left << " + " << right << '\n';
		cin >> n;
	}
}