[백준] 6588 골드바흐의 추측

일단 문제를 보고 생각한 풀이법은 다음과 같다.

1. 소수를 거른다
2. 입력받은 숫자가 n이라면, 홀수 소수의 수열 a(i)에 대해 차례로 검증한다
3. 출력한다

 

1. 소수를 거른다.
딱 떠오른 문제가 있다. 근데 그 방식이 기억이 안 나서 예전에 기록해 두었던 걸 찾았다.
https://github.com/sunnyineverywhere/AltuBitu_Algorithm_Study/blob/main/SEON_UI_LEE/5.%20The%20Number%20Theory/BOJ2960.cpp

GitHub - sunnyineverywhere/AltuBitu_Algorithm_Study

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

vector<int> pn(1000001, 0);

int main(void) {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	pn[0] = 1;
	pn[1] = 1;
	pn[2] = 1;

	for (int i = 2; i * i <= 1000000; i++) {
		if (pn[i] == 0) {
			for (int j = i * i; j <= 1000000; j += i) {
				pn[j] = 1;
			}
		}
	}

	return 0;
}

 

참고해서 코드를 짜면 위와 같다.

 

2. 입력받은 숫자가 n이라면, 홀수 소수의 수열 a(i)에 대해 차례로 검증한다
3. 출력한다

	int n;
	while (1) {
		cin >> n;
		int left = 3;
		int right = n - 3;
		while (left <= right) {
			if (!pn[left] && !pn[right]) {
				if (left + right == n) {
					break;
				}
			}
			left += 2;
			right -= 2;
		}
		if (left > right) {
			cout << "Goldbach's conjecture is wrong.";
		}
		else {
			cout << n << " = " << left << " + " << right;
		}
	}

 

 

답은 맞게 나오는데 계속

출력 초과가 난다...^^

 

이유

n이 0일 때 바로 종료되어야 하는데, 그게 안 되어서 출력 초과(출력 오류)가 났다.

그래서 최종 코드는 while({수정된 부분}) 문만 간단하게 수정하면 된다.

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

vector<int> pn(1000001, 0);


int main(void) {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	pn[0] = 1;
	pn[1] = 1;
	pn[2] = 1;

	for (int i = 2; i * i <= 1000000; i++) {
		if (pn[i] == 0) {
			for (int j = i * i; j <= 1000000; j += i) {
				pn[j] = 1;
			}
		}
	}

	int n = 1;
	while (n != 0) {
		cin >> n;
		if (n == 0) {
			break;
		}
		int left = 3;
		int right = n - 3;
		while (left <= right) {
			if (!pn[left] && !pn[right]) {
				if (left + right == n) {
					break;
				}
			}
			left += 2;
			right -= 2;
		}
		if (left > right) {
			cout << "Goldbach's conjecture is wrong.\n";
		}
		else {
			cout << n << " = " << left << " + " << right << "\n";
		}
	}

	return 0;
}