#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
static const int MAXN = 102;
static const int MAXX = 1e7 + 200;
static const int INF = 0x3fffffff;

int n, x[MAXN];
int m, y[MAXN * 2], k;

bool not_prime[MAXX] = { false };
int primes[MAXX / 10], prime_ct = 0;

inline void sieve()
{
    not_prime[0] = not_prime[1] = true;
    for (int i = 2; i < MAXX; ++i) {
        if (!not_prime[i]) primes[prime_ct++] = i;
        for (int j = 0; j < prime_ct && i * primes[j] < MAXX; ++j) {
            not_prime[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

namespace nwf {

static const int MAXN = ::MAXN * 2 + 2;

int n, source, sink;
struct edge {
    int dest, cap, resi;
    edge() { }
    edge(int dest, int cap, int resi)
        : dest(dest), cap(cap), resi(resi) { }
};
std::vector<edge> e[MAXN];

inline void init(int _n) {
    n = _n;
    for (int i = 0; i < n; ++i) e[i].clear();
}

inline void add_edge(int u, int v, int c, int r = 0) {
    e[u].push_back(edge(v, c, e[v].size()));
    e[v].push_back(edge(u, r, e[u].size() - 1));
}

int lim;
int d[MAXN];

inline bool level_graph() {
    static int q[MAXN], qhead, qtail;
    for (int i = 0; i < n; ++i) d[i] = -1;
    d[source] = 0, q[0] = source, qhead = 0, qtail = 1;

    while (qhead < qtail) {
        int u = q[qhead++];
        for (std::vector<edge>::iterator w = e[u].begin(); w != e[u].end(); ++w)
            if (w->cap >= lim && d[w->dest] == -1) {
                d[w->dest] = d[u] + 1;
                q[qtail++] = w->dest;
            }
    }

    return (d[sink] >= 0);
}

int cur[MAXN];

inline int augment(int u, int cur_cap) {
    if (u == sink) return cur_cap;
    int new_cap;
    for (int &i = cur[u]; i < e[u].size(); ++i) {
        edge &w = e[u][i];
        if (w.cap >= lim && d[w.dest] == d[u] + 1 &&
            (new_cap = augment(w.dest, std::min(w.cap, cur_cap))) >= lim)
        {
            w.cap -= new_cap;
            e[w.dest][w.resi].cap += new_cap;
            return new_cap;
        }
    }
    return 0;
}

inline int deluge() {
    int ans = 0, aug;
    for (lim = 1 << 22; lim > 0; lim >>= 1) {
        while (level_graph()) {
            for (int i = 0; i < n; ++i) cur[i] = 0;
            while ((aug = augment(source, INF)) > 0) ans += aug;
        }
    }
    return ans;
}

}

int main()
{
    sieve();

    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &x[i]);
    y[0] = x[0]; m = 1;
    for (int i = 1; i < n; ++i)
        if (x[i] != x[i - 1] + 1) { y[m++] = x[i - 1] + 1; y[m++] = x[i]; }
    y[m++] = x[n - 1] + 1;

    k = std::partition(y, y + m, [] (int x) { return x & 1; }) - &y[0];

    nwf::init(m + 2);
    nwf::source = m, nwf::sink = m + 1;
    for (int i = 0; i < k; ++i) nwf::add_edge(nwf::source, i, 1);
    for (int i = k; i < m; ++i) nwf::add_edge(i, nwf::sink, 1);
    for (int i = 0; i < k; ++i)
        for (int j = k; j < m; ++j)
            if (!not_prime[std::abs(y[j] - y[i])]) nwf::add_edge(i, j, 1);

    int match = nwf::deluge();
    int ans = match * 1 + ((k - match) / 2) * 2 + ((m - k - match) / 2) * 2 + ((k - match) & 1) * 3;
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 14080