#include <bits/stdc++.h>
using namespace std;

const int maxn=205;
const int maxm=10000005;
const int INF=0x3f3f3f;

int n;
int c[maxm];
int p1[maxn],tot1=0,p2[maxn],tot2=0,nn;

struct Edge
{
    int from,to,capa,flow,next;
}e[maxn*maxn];

int h[maxn],tot=-1;

inline void addedge(int a,int b,int c) { e[++tot].from=a; e[tot].to=b; e[tot].capa=c; e[tot].flow=0; e[tot].next=h[a]; h[a]=tot; }

bool check(int p)
{
    if (p==1) return 0;
    for (int i=2;i*i<=p;i++) if (p%i==0) return 0;
    return 1;
}

int s,t,d[maxn],cur[maxn],vis[maxn];
/*
int dfs(int p,int a)
{
    if (p==t || !a) return a;
    int flow=0,f;
    for (int &i=cur[p];~i;i=e[i].nxt)
    if (d[e[i].to]==d[p]+1 && e[i].capa>e[i].flow)
    {
        f=dfs(e[i].to,min(a,e[i].capa-e[i].flow));
        if (f)
        {
            flow+=f; a-=f;
            e[i].flow+=f; e[i^1].flow-=f;
        }
        if (!a) break;
    }
    if (a) d[p]=-1;
    return flow;
}

int bfs()
{
    queue<int> q;
    memset(vis,0,sizeof(vis));
    q.push(s); vis[s]=1; d[s]=0;
    while (!q.empty())
    {
        int o=q.front(); q.pop();
        for (int i=h[o];~i;i=e[i].nxt)
        if (!vis[e[i].to] && e[i].capa>e[i].flow)
        {
            vis[e[i].to]=1; q.push(e[i].to);
            d[e[i].to]=d[o]+1;
        }
    }
    return vis[t];
}

int Dinic()
{
    int flow=0;
    while (bfs())
    {
        //cout<<"GG";
        for (int i=0;i<=nn;i++) cur[i]=h[i];
        flow+=dfs(s,INF);
    }
    return flow;
}
*/
bool BFS()
{
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s);
    d[s]=0;vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        for(int tmp=h[u];~tmp;tmp=e[tmp].next)
            if(e[tmp].capa>e[tmp].flow&&!vis[e[tmp].to])
            {
                vis[e[tmp].to]=1;
                d[e[tmp].to]=d[u]+1;
                q.push(e[tmp].to);
            }
        q.pop();
    }
    return vis[t];
}

int DFS(int u,int a)
{
    if(u==t||a==0) return a;
    int f,flow=0;
    for(int& tmp=cur[u];~tmp;tmp=e[tmp].next)
        if(d[e[tmp].to]==d[u]+1)
        {
            f=DFS(e[tmp].to,min(a,e[tmp].capa-e[tmp].flow));
            if(f>0)
            {
                flow+=f;a-=f;
                e[tmp].flow+=f;
                e[tmp^1].flow-=f;
                if(a==0) break;
            }
        }
    return flow;
}

int Dinic()
{
    int flow=0;
    while(BFS())
    {
        for(int i=s;i<=t;i++) cur[i]=h[i];
        flow+=DFS(s,INF);
    }
    return flow;
}

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("myout.txt","w",stdout);

    scanf("%d",&n);
    int tmp,mx=0;
    for (int i=1;i<=n;i++) { scanf("%d",&tmp); mx=max(mx,tmp); c[tmp]=1; } mx++;
    //for (int i=mx;i>=1;i--) c[i]=c[i-1]^c[i];
    //for (int i=1;i<=mx;i++) cout<<c[i];
    for (int i=1;i<=mx;i++)
    if (c[i]!=c[i-1])
    {
        if (i&1) p1[++tot1]=i;
            else p2[++tot2]=i;
    }
    //cout<<tot1<<' '<<tot2<<endl;
    nn=tot1+tot2+1; s=0; t=nn;
    //cerr<<"check: "<<s<<" "<<t<<endl;
    //cout<<nn<<endl;
    memset(h,-1,sizeof(h));
    for (int i=1;i<=tot1;i++) { addedge(s,i,1); addedge(i,s,0); }
    for (int i=1;i<=tot2;i++) { addedge(i+tot1,t,1); addedge(t,i+tot1,0); }
    for (int i=1;i<=tot1;i++)
        for (int j=1;j<=tot2;j++)
            if (check(abs(p2[j]-p1[i]))) { addedge(i,j+tot1,1); addedge(j+tot1,i,0); }
    int flow=Dinic(),ans=0;
    //cout<<"GG";
    ans=flow; //cout<<flow<<endl;
    ans+=(tot1-flow)/2*2+(tot2-flow)/2*2;
    ans+=((tot1-flow)&1)*3;
    cout<<ans;
    return 0;
}


Measured memory_bytes: 37248