#include <algorithm>
#include <cstdio>
#include <cstring>
#include <climits>
#include <queue>
#include <vector>

const int N = 202;
const int M = 10000001;

bool is_prime[M];
int x[N], flow[N][N], cost[N][N], dist[N], pred[N];
bool visit[N];

void add_edge(int u, int v, int ca, int co)
{
    flow[u][v] = ca;
    cost[u][v] = co;
    cost[v][u] = -co;
}

int main()
{
#ifdef LOCAL_JUDGE
    freopen("F.in", "r", stdin);
#endif

    memset(is_prime, true, sizeof(is_prime));
    std::vector<int> primes;
    for (int d = 2; d < M; ++ d) {
        if (is_prime[d]) {
            primes.push_back(d);
        }
        for (auto&& p : primes) {
            if (d * p >= M) {
                break;
            }
            is_prime[d * p] = false;
            if (d % p == 0) {
                break;
            }
        }
    }
    is_prime[1] = false;

    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; ++ i) {
            scanf("%d", x + i);
        }
        std::vector<int> odds, evens;

        auto add = [&](int x) {
            (x & 1 ? odds : evens).push_back(x);
        };

        for (int i = 0; i < n; ++ i) {
            if (i == 0 || x[i - 1] != x[i] - 1) {
                add(x[i]);
            }
            if (i + 1 == n || x[i] + 1 != x[i + 1]) {
                add(x[i] + 1);
            }
        }

        // for (int i = 0; i < odds.size(); ++ i) { printf("%d,", odds[i]); } puts("");
        // for (int i = 0; i < evens.size(); ++ i) { printf("%d,", evens[i]); } puts("");

        int s = odds.size() + evens.size();
        int t = s + 1;
        memset(flow, 0, sizeof(flow));
        memset(cost, 0, sizeof(cost));
        for (int i = 0; i < (int)odds.size(); ++ i) {
            add_edge(s, i, 1, 0);
            for (int j = 0; j < (int)evens.size(); ++ j) {
                int d = std::abs(odds[i] - evens[j]);
                add_edge(i, (int)odds.size() + j, 1, is_prime[d] ? 1 : 3);
            }
        }
        for (int i = 0; i < (int)evens.size(); ++ i) {
            add_edge((int)odds.size() + i, t, 1, 0);
        }

        int result = INT_MAX;
        int f = 0, co = 0;
        while (true) {
            int oc = odds.size() - f;
            int ec = evens.size() - f;
            if (oc % 2 == 0 && ec % 2 == 0) {
                result = std::min(result, co + oc + ec);
            }
            for (int i = 0; i <= t; ++ i) {
                dist[i] = INT_MAX;
            }
            dist[s] = 0;
            std::queue<int> queue;
            queue.push(s);
            memset(visit, 0, sizeof(visit));
            while (!queue.empty()) {
                int u = queue.front();
                queue.pop();
                visit[u] = false;
                for (int v = 0; v <= t; ++ v) {
                    if (flow[u][v] > 0 && dist[u] + cost[u][v] < dist[v]) {
                        pred[v] = u;
                        dist[v] = dist[u] + cost[u][v];
                        if (!visit[v]) {
                            visit[v] = true;
                            queue.push(v);
                        }
                    }
                }
            }
            if (dist[t] == INT_MAX) {
                break;
            }
            f ++;
            co += dist[t];
            for (int v = t; v != s; v = pred[v]) {
                int u = pred[v];
                flow[u][v] --;
                flow[v][u] ++;
            }
        }
        printf("%d\n", result);
    }
}

Measured memory_bytes: 16240