// Written By NewbieChd
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int BUF = 1000000;
char buf[BUF], *p1, *p2;
inline char getChar() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BUF, stdin), p1 == p2) ? EOF : *p1++; }
inline int read() {
    int f = 0;
    bool b = 1;
    char c;
    while (!isdigit(c = getChar()))
        if (c == 45)
            b = 0;
    do
        f = f * 10 + (c ^ 48);
    while (isdigit(c = getChar()));
    return b ? f : ~f + 1;
}

const int maxN = 10003, maxE = 4000003, S = maxN - 2, T = maxN - 1, inf = 0x3f3f3f3f;
int cntNode;

int h[maxN], cntEdge = 1;
struct Edge {
    int tar, val, nxt;
    Edge() {}
    Edge(int tar, int val, int nxt) : tar(tar), val(val), nxt(nxt) {}
}ed[maxE];
inline void addEdge(int x, int y, int z) { ed[++cntEdge] = Edge(y, z, h[x]), h[x] = cntEdge, ed[++cntEdge] = Edge(x, 0, h[y]), h[y] = cntEdge; }

int cur[maxN], dep[maxN];
queue<int> que;
inline bool bfs() {
    int i, x, y;
    memset(dep + 1, 0, sizeof(int) * cntNode), memcpy(cur + 1, h + 1, sizeof(int) * cntNode), cur[S] = h[S], dep[S] = 1, dep[T] = 0, que.push(S);
    while (!que.empty()) {
        x = que.front(), que.pop();
        for (i = h[x]; i; i = ed[i].nxt)
            if (ed[i].val && !dep[y = ed[i].tar])
                dep[y] = dep[x] + 1, que.push(y);
    }
    return dep[T];
}
int dfs(int x, int flow) {
    if (x == T)
        return flow;
    int res = flow, k, i, y;
    for (i = cur[x]; i && res; i = ed[i].nxt) {
        cur[x] = i;
        if (ed[i].val && dep[y = ed[i].tar] == dep[x] + 1 && (k = dfs(y, min(res, ed[i].val))))
            res -= k, ed[i].val -= k, ed[i ^ 1].val += k;
    }
    return flow - res;
}

inline int Dinic() {
    int maxFlow = 0, k;
    while (bfs())
        while ((k = dfs(S, inf)))
            maxFlow += k;
    return maxFlow;
}

const int maxL = 10000003, lim = 1e7 + 1;
int prime[maxL];
bool notP[maxL];

bool flag[maxL];
int pos[maxN], ind[maxN];
inline int absolute(int x) { return x >= 0 ? x : ~x + 1; }

int main() {
    int n = read(), cntP = 0, i, j;
    for (i = 2; i <= lim; ++i) {
        if (!notP[i])
            prime[++cntP] = i;
        for (j = 1; j <= lim && i * prime[j] <= lim; ++j) {
            notP[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
    
    for (i = 1; i <= n; ++i)
        flag[read()] = 1;
    for (i = 1; i <= lim; ++i)
        if (flag[i] ^ flag[i - 1])
            pos[++cntNode] = i;
    notP[1] = 1;
    for (i = 1; i <= cntNode; ++i) {
        if (pos[i] & 1) {
            for (j = 1; j <= cntNode; ++j)
                if (!(pos[j] & 1) && (!notP[absolute(pos[i] - pos[j])]))
                    addEdge(i, j, 1);
            addEdge(S, i, 1);
        }
        else
            addEdge(i, T, 1);
        ind[i] = cntEdge ^ 1;
    }
    int ans = Dinic(), tax[2];
    tax[0] = tax[1] = 0;
    for (i = 1; i <= cntNode; ++i)
        if (ed[ind[i]].val)
            ++tax[pos[i] & 1];
    ans += (((tax[0] >> 1) + (tax[1] >> 1)) << 1) + ((tax[0] & 1) | (tax[1] & 1)) * 3;
    
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 24960