C++ 알고리즘 - 백준 6588 골드바흐의 추측

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

 

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

void CPP_INIT() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main(void) {
	CPP_INIT();

	vector<int> prime(1000002);

	for (int i = 2; i < 1000002; i++) {
		prime[i] = i;
	}

	for (int i = 2; i < int(sqrt(1000002)); i++) {
		for (int j = i * i; j < 1000002; j += i) {
			prime[j] = 0;
		}
	}


	int input;
	cin >> input;
	while (input) {
		int num1 = 2;
		int num2 = input;

		while (!prime[num2]) num2--;

		while (num1 + num2 != input) {
			if (num1 + num2 > input) {
				num2--;
				while (!prime[num2]) num2--;

			}

			else if (num1 + num2 < input) {
				num1++;
				while (!prime[num1]) num1++;

			}
		}

		cout << input << " = " << num1 << " + " << num2 << endl;

		cin >> input;
	}
}