백준 / 6588 골드바흐 추측

www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

자기 전에 간단한 문제를 풀어보았습니다.

골드바흐 추측을 표현하라는 문제입니다. 표현 경우가 여러 가지이면, 그 중 두 수의 차가 가장 큰 것을 출력합니다.

입력 값이 6이상인 짝수이므로 골드바흐 추측이 틀린 경우는 없습니다. 

(증명되지는 않았지만, 1,000,000 이하의 수이므로 무조건 통과)

 

에라토스테네스 체를 이용하여 1,000,000까지 소수를 모두 구합니다. 그리고 1,000,000까지 소수들을 탐색하여 처음으로 조건을 만족하는 녀석이 나오면 그걸 출력하면 됩니다. (차이가 가장 큰 것 출력하므로)

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;

int n;
bool prime[1000000];
vector<int>odd_prime;

void make_prime()
{
	memset(prime, true, sizeof(prime));
	prime[0] = false;
	prime[1] = false;
	
	for (int i = 2; i < 1000000; i++) {
		if (prime[i]) {
			for (int j = 2; j * i < 1000000; j++) {
				prime[j * i] = false;
			}
		}
	}

	for (int i = 0; i < 1000000; i++) {
		if (prime[i]) {
			odd_prime.push_back(i);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	make_prime();
	while (1)
	{
		cin >> n;
		if (n == 0)
			break;

		int a = 0;
		int b = 0;

		for (int i = 0; i < odd_prime.size(); i++) {
			if (prime[n - odd_prime[i]]) {
				a = odd_prime[i];
				b = n - a;
				break;
			}
		}

		cout << n << " = " << a << " + " << b << '\n';
	}
}