[백준][수학]골드바흐의 추측

4보다 큰 짝수를 두 소수 홀수의 합으로 출력하는 코드를 작성하는 문제이다. 백만 이하의 수 중에서 소수를 찾기 위해 에라토스테네스의 체를 이용하였다. 에라토스테네스의 체는 소수를 구하는 방법으로 다음과 같다.

 

1. 2부터 n까지의 수를 나열한다.
2. 2의 배수를 제거한다.
3. 제거되지 않은 가장 작은 수(소수)를 찾고 그 수의 배수를 제거한다.
4. 이 행위를 반복하면 n이하의 소수를 구할 수 있다.

#include <iostream>
using namespace std;
const int Max = 1000000; //최대 숫자
bool prime[Max + 1]; //소수 확인

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	prime[0] = prime[1] = true;
	for (int i = 2; i * i <= Max; i++)//에라토스테네스의 체
	{
		if (prime[i] == false) //false 제거되지 않은 수(소수)
		{
			for (int j = i + i; j <= Max; j += i)
			{
				prime[j] = true; //true 제거되는 수(소수X)
			}
		}
	}
	
	int n = 100000;
	while (n--)
	{
		int x;
		cin >> x;

		if (x % 2 == 0 && x>=6)
		{
			for (int i = 3; i <= Max; i += 2) //3:가장 작은 홀수 소수, i+=2 홀수만 확인
			{					
				if (prime[i] == false && prime[x - i] == false)	//x=i+j(i, j: 소수)->x-i:소수		
				{		
					cout << x << " = " << i << " + " << x - i << '\n';
					break;					
				}
			}
		}

		if (x == 0)
			break;
	}
	return 0;
}