#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=510,maxL=10000010,inf=0x3f3f3f3f;
struct cyc{int v,flow,from;}e[maxn*maxn*2];
int tot=1,cnt,n,first[maxn],d[maxn],S,T,num[maxn],b[maxn],cur[maxn];
bool c[maxL];
inline int ab(int x){return x>0?x:-x;}
bool isprime(int x){
    if(x<=2)return 0;
    for(int i=2;i*i<=x;i++)if(x%i==0)return 0;
    return 1;
}
void insert(int u,int v,int w){
    tot++;e[tot].v=v;e[tot].flow=w;e[tot].from=first[u];first[u]=tot;
    tot++;e[tot].v=u;e[tot].flow=0;e[tot].from=first[v];first[v]=tot;
}
queue<int>q;
bool bfs(){
    memset(d,-1,sizeof(d));
    q.push(S);d[S]=0;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=first[x];i;i=e[i].from)
        if(d[e[i].v]==-1&&e[i].flow){
            d[e[i].v]=d[x]+1;
            q.push(e[i].v);
        }
    }
    return d[T]!=-1;
}
int dinic(int x,int a){
    if(x==T||a==0)return a;
    int f,flow=0;
    for(int& i=cur[x];i;i=e[i].from)
    if(d[e[i].v]==d[x]+1&&e[i].flow&&(f=dinic(e[i].v,min(a,e[i].flow)))>0){
        e[i].flow-=f;
        e[i^1].flow+=f;
        a-=f;
        flow+=f;
        if(a==0)break;
    }
    return flow;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){scanf("%d",&num[i]);c[num[i]]=1;}
    for(int i=1;i<=maxL-5;i++)if(c[i]!=c[i-1])b[++cnt]=i;
    S=0;T=cnt+1;
    int m1=0;
    for(int i=1;i<=cnt;i++)if(b[i]&1){
        m1++;
        insert(S,i,1);
        for(int j=1;j<=cnt;j++)if(!(b[j]&1)&&isprime(ab(b[i]-b[j])))insert(i,j,1);
    }else{
        insert(i,T,1);
    }
    int ans=0;
    while(bfs()){
        for(int i=S;i<=T;i++)cur[i]=first[i];
        ans+=dinic(S,inf);
    }
    printf("%d",cnt-ans+(m1-ans)%2);
    return 0;
}