[#9020] 골드바흐의 추측

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
 
    vector<bool> isPrime(10001, true);  //[1]부터 사용. 1이상 10000이하 수가 소수인지 아닌지
    isPrime[1] = false;
 
    //소수 구하기
    for (int i = 2; i <= sqrt(10001); i++) {
        if (isPrime[i]) {
            for (int j = i + i; j < 10001; j = j + i) {
                isPrime[j] = false;
            }
        }
    }
 
 
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;
 
        int small = n / 2;
        int big = n / 2;
 
        while (true) {
            if (isPrime[small] && isPrime[big] && small + big == n)
                break;
        
            --small;
            ++big;
        }
 
        cout << small << " " << big << "\n";
    }
 
    return 0;
}

 

가장 차이가 적은 소수들을 찾는 부분에서 시간초과를 많이 났었음

4 = 2+2

6 = 3+3

8 = 3+5

10 = 5+5

.

.

.

n = ((n/2) - i) + ((n/2) + i) (i>=0)

임을 알고 n을 반으로 쪼개서 하나는 아래로 내려가고, 하나는 위로 올라가는 식으로 검사