/* programed by white-55kai */
#if 0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<utility>
#include<stdlib.h>
#include<time.h>
#else
#include<bits/stdc++.h>
#endif

#if 0
#include<cmath>
#endif

#define REP(i,l,r) for (reg int i=(l);i<=(r);++i)
#define RREP(i,r,l) for (int i=(r);i>=(l);--i)
#define rep(i,l,r) for (int i=(l);i<(r);++i)
#define rrep(i,r,l) for (int i=(r);i>(l);--i)
#define foredge(i,u) for (int i=la[u];i;i=ne[i])
#define mem(a) memset(a,0,sizeof(a))
#define memid(a) memset(a,63,sizeof(a))
#define memax(a) memset(a,127,sizeof(a))
#define dbg(x) cout<<#x<<" = "<<x<<endl
#define reg register
#define tpn typename
#define fr(a) freopen(a,"r",stdin)
#define fw(a) freopen(a,"w",stdout)
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

template <tpn A> inline A Max(const A &x,const A &y){
    return x>y?x:y;
}
template <tpn A> inline A Min(const A &x,const A &y){
    return x<y?x:y;
}
template <tpn A> inline void Swap(A &x,A &y){
    x^=y,y^=x,x^=y;
}
template <tpn A> inline A Abs(const A &x){
    return x>0?x:-x;
}
#if 1
template <tpn A> inline void read(A &x){
    char c;
    A neg=1;
    do{
        c=getchar();
    }while ((c<'0'||c>'9')&&c!='-');
    if (c=='-') neg=-1,c=getchar();
    x=0;
    do{
        x=x*10+c-48;
        c=getchar();
    }while (c>='0'&&c<='9');
    x*=neg;
}
template <tpn A,tpn B> inline void read(A &a,B &b){
read(a),read(b);}
template <tpn A,tpn B,tpn C> inline void read(A &a,B &b,C &c){
read(a),read(b),read(c);}
template <tpn A,tpn B,tpn C,tpn D> inline void read(A &a,B &b,C &c,D &d){
read(a),read(b),read(c),read(d);}
template <tpn A> inline void put(const A &tmp){
    A x=tmp;
    if (x==0){
        putchar('0');
        return;
    }
    if (x<0) putchar('-'),x=-x;
    char buf[30];
    int buf_size=0;
    while (x){
        buf[++buf_size]=x%10+48;
        x/=10;
    }
    RREP(i,buf_size,1) putchar(buf[i]);
}
#else
namespace fastIO {
    #define buf_size 100000
    #define LL long long
    bool error;
    inline char gc() {
        static char buf[buf_size + 1], *l = buf, *r = buf;
        if (l == r) {
            l = buf;
            r = buf + fread(buf, 1, buf_size, stdin);
            if (l == r) {
                error = 1;
                return -1;
            }
        }
        return *l ++;
    }
    inline bool blank(char ch) {
        return ch == '\n' || ch == '\t' || ch == ' ' || ch == '\r' || error;
    }
    inline bool read_int(int &x) {
        char ch;
        int f = 1;
        while (blank(ch = gc()));
        if (error) return false;
        x = 0;
        if (ch == '-') f = -1, ch = gc();
        while (1) {
            x = (x << 1) + (x << 3) + ch - '0';
            if (!isdigit(ch = gc())) break;
        }
        x *= f;
        return true;
    }
    inline bool read_LL(LL &x) {
        char ch;
        LL f = 1;
        while (blank(ch = gc()));
        if (error) return false;
        x = 0;
        if (ch == '-') f = -1, ch = gc();
        while (1) {
            x = (x << 1) + (x << 3) + ch - '0';
            if (!isdigit(ch = gc())) break;
        }
        x *= f;
        return true;
    }
    inline bool read_char(char &x) {
        char ch;
        while (blank(ch = gc()));
        if (error) return false;
        x = ch;
        return true;
    }
    inline void put_int(int x) {
        if (!x) {
            putchar('0');
            return;
        }
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        static int out[13];
        int len = 0;
        while (x) {
            out[++ len] = x % 10;
            x /= 10;
        }
        while (len) putchar(out[len --] + '0');
    }
    inline void put_LL(LL x) {
        if (!x) {
            putchar('0');
            return;
        }
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        static LL out[20];
        int len = 0;
        while (x) {
            out[++ len] = x % 10;
            x /= 10;
        }
        while (len) putchar(out[len --] + '0');
    }
    #undef buf_size
    #undef LL
}
using namespace fastIO;
#endif
inline int mul_mod(int a,int b,int mo){
    int ret;
    __asm__ __volatile__ ("\tmull %%ebx\n\tdivl %%ecx\n":"=d"(ret):"a"(a),"b"(b),"c"(mo));
    return ret;
}
const int N = 10000005, K = 2005, M = 2005005;
int la[K], ne[M], en[M], c[M], edgenum;
int dis[K], cur[K], level[K];
inline void add(int x, int y) {
    ne[++edgenum] = la[x];
    en[edgenum] = y;
    c[edgenum] = 1;
    la[x] = edgenum;
    ne[++edgenum] = la[y];
    en[edgenum] = x;
    la[y] = edgenum;
}
inline void bfs(int S) {
    queue<int> q;
    int u, v;
    while (!q.empty()) q.pop();
    memset(level, -1, sizeof(level));
    level[S] = 0;
    q.push(S);
    while (!q.empty()) {
        u = q.front();
        q.pop();
        foredge(i, u)
        if (c[i] && level[en[i]] < 0) {
            v = en[i];
            level[v] = level[u] + 1;
            q.push(v);
        }
    }
}
int dfs(int u, int t, int f) {
    if (u == t) return f;
    int v, d;
    for (int &i = cur[u]; i; i = ne[i]) {
        v = en[i];
        if (level[v] == level[u] + 1 && c[i]) {
            d = dfs(v, t, min(c[i], f));
            if (d) {
                c[i] -= d;
                c[((i - 1) ^ 1) + 1] += d;
                return d;
            }
        }
    }
    return 0;
}
inline int maxflow(int S, int T) {
    int flow = 0, f;
    while (1) {
        bfs(S);
        if (level[T] < 0) return flow;
        REP(i, S, T) cur[i] = la[i];
        while (f = dfs(S, T, 0x7fffffff)) flow += f;
    }
}
int n, k, x, y, num[K], del[K];
int b[N], pri[N / 10], top;
int main() {
    b[1] = b[2] = 1;
    REP(i, 3, N - 4) {
        if (!b[i] && i & 1) pri[++top] = i;
        if (!(i & 1)) continue;
        for (int j = 1; j <= top && i * pri[j] <= N - 4; ++j) {
            b[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
        }
    }
    read(k);
    REP(i, 1, k) read(num[i]);
    sort(num + 1, num + k + 1);
    REP(i, 1, k) {
        if (i == 1 || num[i - 1] < num[i] - 1) del[++n] = num[i];
        if (i == k || num[i + 1] > num[i] + 1) del[++n] = num[i] + 1;
    }
    REP(i, 1, n) {
        if (del[i] & 1) num[++x] = del[i];
        else del[++y] = del[i];
    }
    REP(i, 1, x) add(1, i + 1);
    REP(i, 1, y) add(i + x + 1, n + 2);
    REP(i, 1, x)
    REP(j, 1, y)
    if (!b[abs(num[i] - del[j])]) add(i + 1, j + x + 1);
    k = maxflow(1, n + 2);
    n = k + 2 * ((x - k) / 2 + (y - k) / 2) + 3 * (x - k & 1);
    cout << n << endl;
    return 0;
}

Measured memory_bytes: 49408