백준 9020 골드바흐의 추측

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 모든 짝수는 두 소수의 합으로 이루어져 있다는 골드바흐의 추측을 만드는 문제입니다. 소수의 합인 경우가 여러가지 나올 경우 두수의 차이가 가장 작은 경우를 출력하라고 하였습니다. n이라는 숫자가 있다면 이 숫자는 n/2 에서 동일하게 떨어져 있는 두 수의 합으로 나타난 다는 것을 알 수 있습니다. 따라서 n이 짝수이므로 n/2에서 한칸씩 앞 뒤로 움직이며 두 수가 모두 소수가 되는 시점이 또한 두 수의 차가 가장 작은 조건도 만족 한다는 것을 알 수 있습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <vector>
//에라토스테네스의 체 

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N = 1;
	bool arr[10000];
	vector<int> v;
	int T;
	cin >> T; 
	
	while(T) {
		fill_n(arr, 10000, true);  
		arr[0] = false;
		arr[1] = false;
		int num = 0;
		int n;
		cin >> n;
		
	for(int i =2; i < n; i++) { //소수부분만 true 저장 
			if(arr[i]) {
				for(int j = i+i; j < n; j+=i)
					arr[j] = false;
			}
		}
	int len = n/2;
	
	for(int i = 0; i < len; i++) //len을 절반으로 나누었을때 len-i와 len+i가 더해져야 n이 될수 있다 
		if(arr[len-i] && arr[len+i]) { //두수 모두가 소수라면 벡터에 삽입 
			v.push_back(len+i);
			v.push_back(len-i);
			break;
		}
		
		cout<<v.back()<<" ";
		v.pop_back();
		cout<<v.back()<<'\n';
		T--;	
	}
	return 0;
}