백준 6588 : 골드바흐의 추측

★★☆☆☆

알고리즘 자체는 어렵지 않았다.

<나의 풀이>

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

int main() {
	int max=1000001;
	bool *prime;
	prime = new bool[max + 1];
	fill_n(prime, max + 1, 1); //모두 true로 설정
	prime[0] = false;
	prime[1] = false;

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for (int i = 2; i <= sqrt(max); i++)
		if (prime[i] == true)
			for (int j = i * 2; j < max; j += i)
				prime[j] = false;

	prime[2] = false; //홀수 소수의 합이므로, 2 제외

	while (1) {
		int x;
		cin >> x;
		bool check = false;
		if (x == 0) break;

		for (int j = 3; j < max; j++) {
			if (prime[j] == true) //소수이면
			{
				if (prime[x - j] == true) { //나머지수도 소수이면
					cout << x << " = " << j << " + " << x - j << "\n";
					check = true;
					break;
				}
			}
		}
		if (check == false) cout << "Goldbach's conjecture is wrong.";
		check = false;
	}

	return 0;
}

지난번에 풀었던 소수구하기 문제를 기반으로 에라토스테네스의 체를 통해 소수를 구한다.
이번에는 bool 배열로 구현해주었다.

구한 소수들을 기반으로 소수의 합을 구하는 코드를 짠다. 여러 숫자의 합이면 애를 먹을뻔 했지만, 두개의 숫자의 합이었기 때문에
단순히 소수 i가 있다면, x-i도 소수인 조합을 찾기만 하면 된다. 그 경우, 반복문을 탈출하며
골드바흐의 추측이 틀리는 경우를 위하여 bool변수 하나를 사용했지만, j값이 max와 같은 경우로 체크할 수도 있다. (bool 변수 사용하는걸 좋아함)

b-a가 가장 큰 값을 출력하라는 조건은, 합을 i가 작은 순서대로 찾아나가기때문에 자연스럽게 만족된다.

시간초과가 나왔지만 ios_base sync_with_stdio 를 false로 설정, tie들도 false 처리 해주니 해결되었다.(다른 알고리즘 상의 시간초과 해결법은 보이지 않았다.)