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

소수에 관한 문제입니다.

2를 제외한 짝수는 소수 두개를 더해서 만들 수 있다고 합니다.
2를 제외한 짝수를 만들때 소수의 두개의 차이를 가장 적게해서
만들 수 있는 수를 출력하는 문제입니다.

1. 소수에 대해서 전부 구합니다.
2. 소수를 벡터에 넣습니다.
3. 소수들끼리 더하면서 찾고 짝수가 나오면 수의 차이와 소수 두개를 저장합니다.
  - 또 나왔을 경우 수의 차이가 적은것의 값과, 소수 두개를 다시 저장합니다.
4. 소수 두개를 출력합니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define MAXSIZE 10010
using namespace std;

int decimal[MAXSIZE];
vector<int> v;

int main(int argc, char *argv[])
{
	int ts;
	int num;
	int check;
	int x, y, z;
	int gap;

	memset(decimal, 0, sizeof(decimal));

	cin >> ts;

	for (int i = 2; i < MAXSIZE; ++i) {
		if (decimal[i] == 0) {
			v.push_back(i);
		}
		for (int j = i * 2; j < MAXSIZE; j += i) {
			decimal[j] = 1;
		}
	}

	while (ts--) {
		gap = 987654321;
		x = 0;
		y = 0;
		z = 0;

		cin >> num;

		for (int i = 0; i < v.size(); ++i) {
			check = i;
			if (v[i] <= num) {
				continue;
			}
			else {
				break;
			}
		}

		for (int i = 0; i < check; ++i) {
			for (int j = i; j < check; ++j) {
				if (v[i] + v[j] == num) {
					z = abs(v[i] - v[j]);
					if (gap > z) {
						gap = z;
						x = v[i];
						y = v[j];
					}
				}
			}
		}

		cout << x << " " << y << endl;
	}

	return 0;
}