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

const int maxn=755;
const int maxm=1e6+10;
const int inf=0x3f3f3f3f;

inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}

inline int q_pow(int A,int B,int P){
    int res=1;
    while(B){
        if(B&1) res=1ll*res*A%P;
        A=1ll*A*A%P;
        B>>=1;
    }
    return res;
}
inline bool check(int A,int P){
    int D=P-1,pw=q_pow(A,D,P);
    if(pw!=1) return false;
    while(!(D&1)){
        D>>=1,pw=q_pow(A,D,P);
        if(pw==P-1) return true;
        else if(pw!=1) return false;
    }
    return true;
}
inline bool Miller_Rabin(int P){
    if(P>14){
        for(int A:{2,3,5,7,11,13}){
            if(!check(A,P)) return false;
        }
        return true;
    }
    else{
        for(int A:{2,3,5,7,11,13}){
            if(P==A) return true;
        }
        return false;
    }
}

int t;
int n;
int a[maxn];
bool mark[maxn];
int S,T;
struct edge{
    int to,nxt,w;
}e[maxm];
int head[maxn],cnt;
inline void add_edge(int u,int v,int w){
    e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt,e[cnt].w=w;
    e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt,e[cnt].w=0;
}
int cur[maxn];
int dis[maxn];
queue<int> q;
int dfs(int u,int rest){
    if(u==T) return rest;
    int flow=0;
    for(int i=cur[u],v,w;i&&rest;i=e[i].nxt){
        cur[u]=i;
        v=e[i].to,w=e[i].w;
        if(dis[u]+1==dis[v]&&w){
            int k=dfs(v,min(rest,w));
            flow+=k,rest-=k;
            e[i].w-=k,e[i^1].w+=k;
        }
    }
    if(!flow) dis[u]=-1;
    return flow;
}
inline int MF(){
    int flow=0;
    while(1){
        memcpy(cur,head,sizeof(head));
        memset(dis,-1,sizeof(dis));
        dis[S]=0;
        q.push(S);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=head[u],v,w;i;i=e[i].nxt){
                v=e[i].to,w=e[i].w;
                if(dis[v]==-1&&w){
                    dis[v]=dis[u]+1;
                    q.push(v);
                }
            }
        }
        if(dis[T]==-1) return flow;
        flow+=dfs(S,inf);
    }
}

int ans;

int main(){
    // freopen("cooking.in","r",stdin);
    // freopen("cooking.out","w",stdout);
    t=1;
    while(t--){
        n=read();
        for(int i=1;i<=n;++i) a[i]=read();
        S=n+1,T=n+2;
        for(int i=1;i<=n+2;++i) head[i]=0;
        cnt=1;
        bool vis1=false;
        ans=0;
        for(int i=1;i<=n;++i){
            mark[i]=false;
            if(a[i]==1){
                if(vis1){
                    mark[i]=true;
                    continue;
                }
                vis1=true; 
            }
            ++ans;
            if(a[i]&1) add_edge(S,i,1);
            else add_edge(i,T,1);
        }
        for(int i=1;i<=n;++i){
            if(mark[i]) continue;
            for(int j=i+1;j<=n;++j){
                if(mark[j]) continue;
                if(Miller_Rabin(a[i]+a[j])){
                    if(a[i]&1) add_edge(i,j,inf);
                    else add_edge(j,i,inf);
                }
            }
        }
        ans-=MF();
        printf("%d\n",ans);
    }
    return 0;
}