백준 / 수학 / 6588번 / 골드바흐의 추측 / C++

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는

편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다.

또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다.

숫자와 연산자는 공백 하나로 구분되어져 있다.

만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다.

또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

예제 입력 1 

8

20

42

0

예제 출력 1 

8 = 3 + 5

20 = 3 + 17

42 = 5 + 37

 

#include <iostream>
#define N 1000001
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	string wrong = "Goldbach's conjecture is wrong.";
	
	bool arr[N];
	for(int i=0; i<N; i++) {
		arr[i] = true;
	}
	arr[0] = arr[1] = false;
	
	for(int i=2; i*i<N; i++) { // 1
		if(arr[i]) {
			for(int j=i*2; j<N; j+=i) {
				arr[j] = false;
			}
		}
	}
	
	while(true) { // 2
		int n;
		int a, b;
		
		cin >> n;
		
		if(!n) break;
		
		for(int i=3; i<=n; i+=2) {
			a = i;
			b = n - i;
			
			if(b < 0) {
				cout << wrong << '\n';
				break;
			}
			else if(arr[a] && arr[b]) {
				cout << n << " = " << a << " + " << b << '\n';
				break;
			}
		}
	}

	return 0;
}

---

하 진짜 이문제는 하루종일 잡고 있었던것 같다.

사실 알고리즘 구현은 진작에 끝났었는데 시간초과와 런타임에러가 계속 났다.

 

일단, 소수 구하는 알고리즘은 밑의 포스팅을 참조하면 좋을것같다.

2022.01.16 - [ALGORITHM/개념] - 에라토스테네스의 체

에라토스테네스의 체

 

while문 안을 살펴보면 일단 입력을 받고, 0일시 바로 break를 걸어주어 종료시킨다.

이제야 생각난건데 while(true)해서 안에 break문을 따로 만드는것 대신 while(cin >> n) 할걸 그랬다.

 

그리고 for문을 보면, 우리는 소수중에서도 홀수만 찾으면 되기 때문에, 3, 5, 7, 9... 식으로 반복문을 돌았다.

그리고 a = i, b = n - i가 그냥 보면 이해가 안될수도 있는데 간단하다.

a와 b의 합이 n이 되야하므로 저렇게 된다.

그것을 이용해 a는 처음부터 수가 증가하고, b는 n부터 수가 감소할 것이다.

 

그리고 소수 배열에서 a번째 element가, 즉 a가 소수이고 b번째 element, 즉 b가 소수라면 출력해주면된다.

 

이제 내가 시간초과와 런타임에러가 계속 났던이유를 설명해보겠다.

 

일단 지금 코드를 보면 소수를 구하는 배열 초기화를 while문 밖에서 해주었다.

하지만 시간초과 났을때는 while문 안에서 n을 입력받고, n까지의 배열만 초기화 하려했기 때문에

아래와 같이 저 for문(주석(1))이 while문(주석(2))안에 있었다.

#include <iostream>
#define N 1000001
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	string wrong = "Goldbach's conjecture is wrong.";
	
	bool arr[N];
	for(int i=0; i<N; i++) {
		arr[i] = true;
	}
	arr[0] = arr[1] = false;
	
	while(true) { // 2
		int n;
		int a, b;
		
		cin >> n;
		
		if(!n) break;
		
        	for(int i=2; i*i<n; i++) { // 1
			if(arr[i]) {
				for(int j=i*2; j<n; j+=i) {
					arr[j] = false;
				}
			}
		}
        
		for(int i=3; i<=n; i+=2) {
			a = i;
			b = n - i;
			
			if(b < 0) {
				cout << wrong << '\n';
				break;
			}
			else if(arr[a] && arr[b]) {
				cout << n << " = " << a << " + " << b << '\n';
				break;
			}
		}
	}

	return 0;
}

그래서 새로운 n값을 입력받을때마다 반복문을 또 돌았기 때문에 시간초과가 났던것이다.

 

두번째로 런타임에러가 났던이유는 매우 허무했다.

#define N 에서 0을 하나 빼먹었다....

테스트의 갯수와 n의 최댓값을 순간적으로 헷갈려 저렇게 적어놓고 찾지못하다가 겨우 발견했다.

혹시 만약 시간초과나 런타임에러 때문에 참고하는 분들은 위의 부분을 꼭 확인하길 바란다.