[C++] 백준 6588번: 골드바흐의 추측

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

6588번: 골드바흐의 추측

최초풀이

처음 prime 배열을 활용하여 2-1,000,000까지의 모든 소수를 구합니다.(에라토스테네스의 체)

또한 별도의 벡터를 활용하여 소수들만 따로 뽑아줍니다.

추가적으로 시간초가 에러에 대해서는 아래의 코드와

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

endl 대신 "\n"을 활용하여 처리하여 해결하였습니다.

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

bool prime[1000001];
//1,000,000이하의 수

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

	memset(prime, true, sizeof(prime));
	vector<int>prime_;
	int k = 1;

	for (int i = 2; i <= 1000; i++) {
		for (int j = 2; j * i <= 1000000; j++)
			prime[j * i] = false;
	}

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

	while (1) {
		cin >> k;
		if (k == 0)break;
		for (int i = 0; i < prime_.size(); i++) {
			if (k > prime_[i] && prime[k - prime_[i]]) {
				cout << k << " = " << prime_[i] << " + " << k - prime_[i] << "\n";
				break;
			}
		}
	}

	return 0;
}