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

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

6588번: 골드바흐의 추측

 

#include <iostream>
using namespace std;
#define MAX 1000000
int arr[MAX] = { 0, };
int main() {
 
	arr[0] = arr[1] = 1;
 
	for (int i = 2;i * i < MAX / 2;i++) {
		if (arr[i])
			continue;
		else
			for (int j = 2; i * j <= MAX / 2; ++j) {
				arr[i * j] = 1;
			}
	}
 
	int a;
 
	for (int T = 1;T <= 100000;T++) {
		bool b = false;
		cin >> a;
		if (a == 0)
			break;
		else {
			for (int i = 3;i < a / 2;i += 2) {
				if (arr[i] == 0 && arr[a - i] == 0) {
					cout << a << " = " << i << " + " << a - i << "\n";
					b = true;
					break;
				}
			}
			if (!b)
				cout << "Goldbach's conjecture is wrong. \n";
		}
	}
 
	return 0;
}

 

저번에 풀었던 에라토스테네스의 체를 이용하여 백만까지의 소수를 구해준다음 대입해서 풀었는데 시간초과가 떴다. 

 

#include <iostream>
using namespace std;
 
#define MAX 1000000
bool arr[MAX] = { false, };
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); 
	cout.tie(NULL);
 
	arr[0] = arr[1] = 1;
 
	for (int i = 2;i * i <= MAX;i++) {
		if (arr[i])
			continue;
		
			
		for (int j = i*i; j < MAX; j += i) {
			arr[j] = 1;
		
		}
	}
 
	int a;
 
	while (true) {
		cin >> a;
		if (a == 0)
			break;
 
		bool b = false;
 
		for (int i = 3;i <= a ;i += 2) {
			if (!arr[i] && !arr[a - i]) {
				cout << a << " = " << i << " + " << a - i << "\n";
				b = true;
				break;
			}
		}
		if (!b)
			cout << "Goldbach's conjecture is wrong. \n";
	}
 
	return 0;
}

 

조금조금씩 수정하다 보니 성공했다.

 

 

백준 문제중에 가장 의외로 가장 많이 시도했던 문제였다.

 

틀렸던이유

 

1) 에라토스의 체를 사용하는 과정에서 50만 더하기 50만이 백만인데 구해야 되는 소수는 50만 까지라고 생각이 되서 했던게 일단 실수였다.