#pragma GCC optimize(3)
#include<iostream>
#include<iomanip>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set> 
#include<map>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define ll long long
#define db double
#define inf 10000001
#define infm 50001
#define INF (int)1e8 
#define mod (int)(1e9+7)
#define pi acos(-1)
#define rd(n) {n=0;char ch;int f=0;do{ch=getchar();if(ch=='-'){f=1;}}while(ch<'0'||ch>'9');while('0'<=ch&&ch<='9'){n=(n<<1)+(n<<3)+ch-48;ch=getchar();}if(f)n=-n;}
using namespace std;
 
int p[inf],ckp[inf],pcnt;
const int lim=10000000;
 
void pre_work(void){
    ckp[0]=ckp[1]=1;
    for (int i=2;i<=lim;i++){
        if (!ckp[i]){
            p[++pcnt]=i;
        }
        for (int j=1;j<=pcnt && p[j]*i<=lim;j++){
            ckp[p[j]*i]=1;
            if (i%p[j]==0){
                break;
            }
        }
    }
    return;
}
 
int S,T;
 
struct edge{
    int nxt,y,s;
}e[infm*2];
int ecnt=1,head[infm],h[infm];
 
void addedge(int x,int y,int s){
    ecnt++;
    e[ecnt].nxt=head[x];
    e[ecnt].y=y;
    e[ecnt].s=s;
    head[x]=ecnt;
    return;
}
 
void ae(int x,int y,int s){
    addedge(x,y,s);
    addedge(y,x,0);
    return;
}
 
queue <int> q;
int dep[inf];
 
int dfs(int u,int flow){
    if (!flow || u==T){
        return flow;
    }
    int ans=0;
    for (int i=h[u];i;i=e[i].nxt){
        h[u]=i;
        int v=e[i].y,s=e[i].s,now;
        if (dep[v]!=dep[u]+1){
            continue;
        }
        now=dfs(v,min(flow,s));
        if (now){
            ans+=now;
            flow-=now;
            e[i].s-=now;
            e[i^1].s+=now;
            if (!flow){
                break;
            }
        }
    }
    return ans;
}
 
int dinic(void){
    int ans=0;
    while (1){
        while (!q.empty()){
            q.pop();
        }
        memcpy(h,head,sizeof(head));
        memset(dep,-1,sizeof(dep));
        dep[S]=0;
        q.push(S);
        while (!q.empty()){
            int u=q.front(),v,s;
            q.pop();
            for (int i=head[u];i;i=e[i].nxt){
                v=e[i].y,s=e[i].s;
                if (dep[v]<0 && s){
                    dep[v]=dep[u]+1;
                    q.push(v);
                }
            }
        }
        if (dep[T]<0){
            break;
        }
        ans+=dfs(S,INF);
    }
    return ans;
}
 
int n;
int a[inf];
int L[inf],R[inf];
 
int main(){
    pre_work();
    rd(n)
    int x,mx=0;
    for (int i=1;i<=n;i++){
        rd(x)
        a[x]++;
        mx=max(mx,x);
    }
    int cntl=0,cntr=0;
    for (int i=1;i<=mx+1;i++){
        if (a[i]!=a[i-1]){
            if (i&1){
                L[++cntl]=i;
            }
            else{
                R[++cntr]=i;
            }
        }
    }
    S=0,T=cntl+cntr+1;
    for (int i=1;i<=cntl;i++){
        ae(S,i,1);
    }
    for (int i=1;i<=cntr;i++){
        ae(i+cntl,T,1);
    }
    for (int i=1;i<=cntl;i++){
        for (int j=1;j<=cntr;j++){
            if (!ckp[abs(L[i]-R[j])]){
                ae(i,j+cntl,1);
            }
        }
    }
    int mxf=dinic();
    int ans=mxf;
    ans+=(cntl-mxf)/2*2+(cntr-mxf)/2*2;
    ans+=((cntl-mxf)&1)*3;
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 125184