Nguyen Xuan Nghia

//DQBN22
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=(int)1e6+7;
int a[N],n,f[N];
ll res=0;

void snt(){
    for (int i=1;i<=N;++i) f[i]=0;
    f[1]=1;
    for (int i=2;i<=N/i;++i)
        if (f[i]==0)
            for (int j=2;j<=N/i;++j)
                f[i*j]=1;
}

void try2(ll sum,int pos){
    for (int i=pos;i<=n;++i){
        sum=sum+a[i];
        if (f[sum]==0) res=max(res,sum);
        //sum=sum+a[i];
        try2(i,sum);
    }
}

int main()
{
    cin>>n;
    for (int i=1;i<=n;++i)
        cin>>a[i];
    snt();
    try2(1,0);
    cout<<res;
    return 0;
}

//DQBN22(2)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=(int)1e6+7;
ll s=0,res=0;
int a[N],n,f[N],b[N];

void snt(int N){
    for (int i=1;i<=N;++i) f[i]=0;
    f[1]=1;
    for (int i=2;i<=N/i;++i)
        if (f[i]==0)
            for (int j=2;j<=N/i;++j)
                f[i*j]=1;
}

void xet(){
    ll s=0;
    for (int i=1;i<=n;++i)
        if (b[i]==1) s+=a[i];
    if (f[s]==0){
        for (int i=1;i<=n;++i)
            if (b[i]==1) cout<<a[i]<<" ";
    cout<<"\n";}
}

void sinh(int d){
    for (int i=0;i<=1;++i){
        b[d]=i;
        if (d==n) xet();
        else sinh(d+1);
    }
}

int main()
{
    cin>>n;
    for (int i=1;i<=n;++i) cin>>a[i],s+=a[i];
    snt(s);
    sinh(1);
}