BOJ : 9020 골드바흐의 추측

---

[BOJ 9020(S1) 리뷰]

소수관련 문제를 풀다가 풀게 된 문제이다.

문제는 설명에 나온대로 2이상의 짝수가 주어지면 그 짝수는 소수 두개의 합으로 이루어진다는것이다.

예를들어 14는 3+11로 이루어지며 10은 5+5로 이루어진다. 만약 짝을 이루는 소수가 두개라면 두 소수간의 차이가 적은것을 출력하면 된다.

 

나는 소수인지 판별하는 val값을 2부터 n-1까지 증가시키며 만약 val이 소수일경우 n-val의 값이 소수인지 확인 후 그 값이 소수라면 출력하도록 했다. 예를들어 n이 8이라면 2부터 7까지 소수인지 확인을 한다. 3이 소수이므로 isUsed[3]=1이 되고 또 증가하며 5가 소수이고 isUsed[8-5]가 1이므로 두 수를 출력하면 된다.

루프를 돌때마다 확인배열을 초기화시켜주면 가장 가까운 소수 두개를 출력할 수 있다.

 

나는 이렇게 풀었으나 시간이 오래걸렸다. 더 좋은 풀이를 찾아보니 먼저 2부터 10000까지 소수를 판별하여 확인배열에 담아두고 n/2를 한다음 한쪽은 증가,한쪽은 감소하여 소수를 만나면 출력하도록 하는 방법도 있다.

---

#include <iostream>
#include <queue>
#include <string>
#include <stack>
#include <math.h>
using namespace std;
bool isUsed[100001];

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	int T;
	cin >> T;
	while (T--)
	{
		int n;
		cin >> n;
		for (int val = 2; val < n; val++)
		{
			if (isUsed[val]) continue;
			int ret = true;
			for (int i = 2; i <= sqrt(val); i++)
			{
				if (val % i == 0)
				{
					ret = false;
					break;
				}
			}
			if (ret)
			{
				isUsed[val] = 1;
				if (isUsed[n - val])
				{
					cout << n - val << ' ' << val << '\n';
					break;
				}
			}
		}
		fill(isUsed, isUsed + n, 0);
	}

}