6588번 골드바흐의 추측 with C++

문제

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

6588번: 골드바흐의 추측

 

해결한 방법

1. 전 문제인 소수 구하기에서의 방법으로 소수 리스트를 만듭니다.
2. 소수 리스트에서 하나씩 가져와서 input에서 뺀 값이 소수라면 n = a + b형식으로 출력합니다.
3. 소수 리스트 끝에 도달해도 출력하지 못한다면 "Goldbach's conjecture is wrong."를 출력합니다.

#include <iostream>
#include <cmath>
#define MAX 1000001
using namespace std;

int input_li[100001];
bool prime[MAX];
int prime_li[MAX];

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

	int input_count = -1;
	int max = 0;
	do{
		input_count++;
		cin >> input_li[input_count];
		if (max < input_li[input_count])
			max = input_li[input_count];
	} while (input_li[input_count]);

	fill_n(prime, MAX, 1);
	prime[0] = false;
	prime[1] = false;

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

	int prime_count = 0;
	for (int i = 0; i <= max; i++){
		if (prime[i]) {
			prime_li[prime_count] = i;
			prime_count++;
		}
	}

	bool is_wrong = true;
	for (int i = 0; i < input_count; i++) {
		for (int j = 0; j < prime_count; j++) {
			if (prime[input_li[i] - prime_li[j]]) {
				cout << input_li[i] << " = " << prime_li[j] << " + " << input_li[i] - prime_li[j] << "\n";
				is_wrong = false;
				break;
			}
		}
		if (is_wrong) {
			cout << "Goldbach's conjecture is wrong." << "\n";
		}
		is_wrong = true;
	}


	return 0;
}