백준 6588 c++ 골드바흐의 추측

 

문제를 설명하자면

주어진 입력값에 대해

홀수인 소수의 합으로 나타낼수 있는 값중

가장 차가 큰 합으로 나타내라는 것이다

그리고, 홀수인 소수의 합으로 나타낼 수 없으면 문구를 출력한다

 

 

예를들어 10을 홀수인 소수로 나타내라고하면

10 = 3 + 7

10 = 5 + 5

로 나타낼 수 있다(7 + 3은 없다 a + b형태에서 b가 더 크도록 나타내기때문)

여기서 차이가 큰 것은 5 + 5 보다 3 + 7이다

5+5는 차이가 0이고 3+7은 차이가 4기 때문이다

 

그래서

소수를 판별하는 방법에 에라토스테네스의 체를 이용했고,

n으로부터 가장 가까운 홀수인 소수를 찾고

n-소수가 홀수이고 소수를 만족하면

반복문을 탈출해 

합으로 나타냈다

 

그 외에 반복문을 다 돌았는데도

값이 변하지 않으면 홀수인 소수로 나타낼 수 없으므로 문구를 출력해준다

 

그리고 홀수는 두 홀수의 합으로 나타낼 수 없으므로

홀수가 들어오면 바로 반복문을 탈출해주고 문구를 출력한다

 

#include <iostream>
#define MAX 1000000
using namespace std;

bool arr[MAX + 1];

void Eratos(int n);
void Goldbach(int n);

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int input = 1;
	Eratos(MAX);
	while (true) {
		cin >> input;
		if (input == 0)
			break;
		Goldbach(input);
	}



	return 0;
}

void Eratos(int n) {


	for (int i = 0; i <= n; i++) {		//처음엔 다 소수로
		arr[i] = true;
	}
	arr[0] = false;
	arr[1] = false;


	for (int i = 2; i * i <= n; i++) {
		if (arr[i]) {	//소수이면
			for (int j = i * i; j <= n; j += i) {
				arr[j] = false;
			}
		}
	}



}

void Goldbach(int n) {
	int max_a = 0, max_b = -1;
	int a, b;


	for (int i = n-3; i >= 2; i--) {

		if (n % 2 != 0)
			break;


		if (arr[i] && i % 2 != 0) {	//소수이고 홀수인 수중에
			b = i;
			a = n - b;	//max_b는 n-max_a로 가정

			if (arr[a] && a % 2 != 0) { //max_b도 소수고 홀수이면

				if (b - a > max_b - max_a) { //차가최댓값되는 값만 저장
					max_a = a;
					max_b = b;
				}
				break;
			}
			else {		//a만 홀수&소수면 포함안됨
				a = 0;
				b = 0;
			}
		}


	}

	if (max_b - max_a == -1) {
		cout << "Goldbach's conjecture is wrong." << "\n";
	}
	else {
		cout << n << " = " << max_a << " + " << max_b << "\n";
	}
}