※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
i번째 수와 j번째 수를 더하여 소수가 될 때, 이를 i→j로 그래프를 연결시킨다고 생각해 봅니다. 그 다음, 1번째 수와 어느 수가 연결되어 있다면, 카운트 1을 해준 뒤 해당 지점을 방문한 것으로 체크합니다. 그 다음 나머지 점을 기준으로 최대 이분 매칭 알고리즘을 통해 얼마나 매칭되는지 검사합니다.
만약 모든 쌍이 소수가 될 수 있다면 $n$개의 수에 대해 먼저 매칭시켰던 1번째 수와 나머지 수를 제외한 수가 모두 매칭되었으므로 $n-2$개가 매칭됨을 확인할 수 있습니다. 최대 매칭 수가 $n-2$라면 1번째 수와 매칭시켰던 수를 정답으로 추가시킵니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int g[50][50],n,l[50],match[50];
bool s[50];
bool isPrime(int n)
{
for(int i=2; i*i<=n;i++)
if(n%i==0)return false;
return true;
}
bool bpm(int u)
{
for(int v=1;v<n;v++)
{
if(g[u][v]&&!s[v]&&!s[u])
{
s[v]=true;
if((match[v]<0)||bpm(match[v]))
{
match[v]=u;
return true;
}
}
}
return false;
}
int maxBPM(int x)
{
memset(match,-1,sizeof(match));
match[0]=match[x]=0;
int r=0;
for(int u=1;u<n;u++)
{
memset(s,0,sizeof(s));
s[0]=1;
if(bpm(u))r++;
}
return r;
}
int main()
{
vector<int> v;
cin>>n;
for(int i=0;i<n;i++)cin>>l[i];
sort(l+1,l+n);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(isPrime(l[i]+l[j]))g[i][j]=g[j][i]=1;
for(int i=0;i<n;i++)
{
if(g[0][i])
{
int r=maxBPM(i);
if(r==n-2)v.push_back(l[i]);
}
}
if(!v.size())cout<<"-1";
else for(int i=0;i<v.size();i++)cout<<v[i]<<" ";
}