백준 9020번 골드바흐의 추측

🔒문제 url

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

🪄전체 코드

#include <iostream>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int t,n;
int notPrime[10001];

void INPUT()
{
    IAMFAST
    cin >> t;
}

void eratos()
{//에라토스테네체의 체
    for(int i = 2; i*i <= 10000; i++)
    {
        if(notPrime[i]) continue;
        for (int j = i*i; j <= 10000; j+=i)
            notPrime[j] = true;
    }
}

void SOLVE()
{
    eratos();

    while(t--)
    {
        cin >> n;

        pair<int,int> ans = {0,0};
        for(int i = n/2; i >= 2; i--)
        {//차가 작은 숫자부터 탐색
            if(!notPrime[i]&& !notPrime[n - i])
            {//i와 n-i둘 다 소수이면 답 갱신 후 탐색 종료
                ans = {i,n-i};
                break;
            }
        }
        //출력
        cout << ans.first << " " << ans.second << '\n';
    }
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.