#include <bits/stdc++.h>

using namespace std;

struct littlstar{

    int to;

    int nxt;

    int w;

}star[];

int head[],cnt=;

void add(int u,int v,int w)

{

    star[++cnt].to=v;

    star[cnt].nxt=head[u];

    star[cnt].w=w;

    head[u]=cnt;

}

int n;

int prime[];

int a[];

void pre()

{

    for(register int i=;i<=;i++){

        if(prime[i]) continue;

        for(register int j=i;j<=/i;j++){

            prime[i*j]=;

        }

    }

}

int dis[];

queue<int> q;

bool bfs()

{

    memset(dis,,sizeof(dis));

    while(q.size()) q.pop();

    q.push();

    dis[]=;

    while(q.size())

    {

        int u=q.front();

        q.pop();

        for(register int i=head[u];i;i=star[i].nxt){

            int v=star[i].to;

            if(star[i].w&&!dis[v]){

                q.push(v);

                dis[v]=dis[u]+;

                if(v==) return ;

            }

        }

    }

    return ;

}

int dinic(int u,int flow)

{

    if(u==){

        return flow;

    }

    int rest=flow,k;

    for(register int i=head[u];i&&rest;i=star[i].nxt){

        int v=star[i].to;

        if(star[i].w&&dis[v]==dis[u]+){

            k=dinic(v,min(rest,star[i].w));

            if(!k) dis[v]=;

            star[i].w-=k;

            star[i^].w+=k;

            rest-=k;

        }

    }

    return flow-rest;

}

int maxflow=;

int b[];

int main ()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        scanf("%d",&a[i]);

    }

    sort(a+,a++n);

    int tmpnum=;

    for(int i=;i<=n;i++){

        if(i>&&a[i]==){

            continue;

        }

        b[++tmpnum]=a[i];

    }

    n=tmpnum;

    for(int i=;i<=n;i++){

        a[i]=b[i];

    }

    pre();

    for(register int i=;i<=n;i++){

        for(register int j=;j<=n;j++){

            if(i==j) continue;

            if(!prime[a[i]+a[j]]&&a[i]%==&&a[j]%==){

                add(i,j,);

                add(j,i,);

            }

        }

    }

    for(register int i=;i<=n;i++){

        if(a[i]%==){

            add(,i,);

            add(i,,);

        }

        else{

            add(i,,);

            add(,i,);

        }

    }

    int flow=;

    while(bfs()){

        while(flow=dinic(,)){

            maxflow+=flow;

        }

    }

    cout<<n-maxflow;

}