9020 골드바흐의 추측

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

골드바흐의 추측은 2보다 큰 모든 짝수는 두 개의 소수의 합으로 나타낼 수 있다는 것이다. 아직 정수론의 미해결 문제로 현재까지 10^18 이하에서 참이라는 것을 확인했다고 한다. 에라토스테네스의 체로 소수를 미리 구한후 n의 절반부터 줄여가면서 i와 n-i가 소수가 되는지 확인한다. 이 때 처음 발견하는 골드바흐 파티션이 두 소수의 차이가 최소이다.

#include <cstdio>
 
bool p[10001];
int t,n;
 
int main()
{
    p[0]=p[1]=true;
    for(int i=2;i*i<10001;i++) if(!p[i]) for(int j=2*i;j<10001;j+=i) p[j]=true;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=n/2;i>=2;i--)
        {
            if(!p[i] && !p[n-i])
            {
                printf("%d %d\n",i,n-i);
                break;
            }    
        }
    }
    return 0;
}