#include <cstdio>
#include <cstring>
#include <algorithm>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
using namespace std;

int tot,n,m,t[110],a[110],b[110],prm[10010],map[110][110],link[110],ans;
bool flag[10010];

void insert(int x)
{
    (x&1?a[++n]:b[++m])=x;
}

bool check(int x)
{
    if (x<=2)
        return 0;
    for (int i=1; prm[i]*prm[i]<=x; ++i)
        if (!(x%prm[i]))
            return 0;
    return 1;
}

bool hungary(int x)
{
    repu(i,1,map[x][0])
        if (!flag[map[x][i]])
        {
            flag[map[x][i]]=1;
            if (!link[map[x][i]] || hungary(link[map[x][i]]))
            {
                link[map[x][i]]=x;
                return 1;
            }
        }
    return 0;
}

int main()
{
    scanf("%d",&tot);
    repu(i,1,tot)
        scanf("%d",&t[i]);
    for (int i=1,j; i<=tot; i=j+1)
    {
        for (j=i; j<tot && t[j+1]==t[j]+1; ++j);
        insert(t[i]),insert(t[j]+1);
    }
    tot=0;
    repu(i,2,1e4)
        if (!flag[i])
        {
            prm[++tot]=i;
            for (int j=i*2; j<=1e4; flag[j]=1,j+=i);
        }
    repu(i,1,n)
        repu(j,1,m)
            if (check(abs(a[i]-b[j])))
                map[i][++map[i][0]]=j;
    repu(i,1,n)
    {
        memset(flag,0,sizeof(bool)*(m+10));
        ans+=hungary(i);
    }
    printf("%d\n",n+m-ans+((n-ans)&1));
    return 0;
}