BaekJoon(9020)::골드바흐의 추측

문제

9020번: 골드바흐의 추측

문제 파악

1. 해당 문제는 제목에서도 말하듯이 골드바흐의 추측을 통해 해결할 수 있다.
2. 골드바흐의 추측은 2보다 큰 짝수는 두소수의 합으로 나타낼수 있다는 추측으로 해당 수를 골드바흐 수라고 한다.
3. 주어진 골드바흐의 수는 두 소수의 합들로 나타낼 수 있다.
4. 여러 소수쌍중 해당 값의 차이가 가장 작은 것을 출력한다.

위 정리에서 알 수 있듯 우선 소수판별을 위해 에라테토스테네스의 체를 먼저 작성한다.

문제풀이

#include <iostream>
#include <cmath>

using namespace std;

int p_arr[10001] = { 0, };			

void soe() {				
	p_arr[0] = p_arr[1] = 1;
	for (int i = 2; i < sqrt(10001);i++) {
		if (p_arr[i] == 0) {
			for (int j = i * 2; j < 10001; j += i) {
				p_arr[j] = 1;
			}
		}
	}
}

int main()
{
	int t;				
	int n;

	cin >> t;
	soe();

	while (t--) {
		cin >> n;
		int num1 = -1, num2 = -1;
		int min = n;

		for (int i = 2; i <= (n+1)/2;i++) {
			if (p_arr[i] == 0 && p_arr[n-i] ==0) {
				if (min > n - (2*i)) {
					min = n - (2 * i);
					num1 = i;
					num2 = n-i;
				}
				
			}
		}
		cout << num1 << " " << num2 << endl;
	}
}

 

문제풀이시 타임아웃을 경험할 수 있다.

이유는 두수의 합이 소수임을 확인하기 위해 만약 for문을 이중으로 수행 할 경우 발생한다.

→ 하나의 수(i)가 소수일 경우 (n-i) 또한 소수여야 함을 이용하여 이중 for문의 수행을 방지하면된다.