#include <bits/stdc++.h>
using namespace std;

int x[105], n;
vector<int> vt[2];
bool notprime[100000015];
bool X[10000015];

void add(int t)
{
    if (X[t]) return;
    X[t] = true;

    bool a = binary_search(x, x + n, t);
    bool b = binary_search(x, x + n, t - 1);
    if (a != b) vt[t & 1].push_back(t);
}

// in: n, m, graph
// out: match, matched
// vertex cover: (reached[0][left_node] == 0) || (reached[1][right_node] == 1)
// O(E*sqrt(V))
struct BipartiteMatching {
    int n, m;
    vector<vector<int>> graph;
    vector<int> matched, match, edgeview, level;
    vector<int> reached[2];
    BipartiteMatching(int n, int m) : n(n), m(m), graph(n), matched(m, -1),
    match(n, -1) {}
    bool assignLevel() {
        bool reachable = false;
        level.assign(n, -1);
        reached[0].assign(n, 0);
        reached[1].assign(m, 0);
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (match[i] == -1) {
                level[i] = 0;
                reached[0][i] = 1;
                q.push(i);
            }
        }
        while (!q.empty()) {
            auto cur = q.front(); q.pop();
            for (auto adj : graph[cur]) {
                reached[1][adj] = 1;
                auto next = matched[adj];
                if (next == -1) {
                    reachable = true;
                }
                else if (level[next] == -1) {
                    level[next] = level[cur] + 1;
                    reached[0][next] = 1;
                    q.push(next);
                }
            }
        }
        return reachable;
    }
    int findpath(int nod) {
        for (int &i = edgeview[nod]; i < graph[nod].size(); i++) {
            int adj = graph[nod][i];
            int next = matched[adj];
            if (next >= 0 && level[next] != level[nod] + 1) continue;
            if (next == -1 || findpath(next)) {
                match[nod] = adj;
                matched[adj] = nod;
                return 1;
            }
        }
        return 0;
    }
    int solve() {
        int ans = 0;
        while (assignLevel()) {
            edgeview.assign(n, 0);
            for (int i = 0; i < n; i++)
                if (match[i] == -1)
                    ans += findpath(i);
        }
        return ans;
    }
};


int main()
{
    notprime[1] = true;
    for (int i = 3; i <= 10000010; i += 2)
    {
        if (notprime[i]) continue;
        for (int j = i * 3; j <= 10000010; j += i * 2)
            notprime[j] = true;
    }

    scanf("%d",&n);
    for (int i = 0; i < n; i++) scanf("%d", &x[i]);
    sort(x, x + n);

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

    if (vt[0].empty() || vt[1].empty())
    {
        printf("%zd\n", vt[0].size() + vt[1].size());
        return 0;
    }

    BipartiteMatching bm(vt[0].size(), vt[1].size());
    for (int i = 0; i < vt[0].size(); i++)
    {
        for (int j = 0; j < vt[1].size(); j++)
        {
            if (notprime[abs(vt[0][i] - vt[1][j])] == false)
                bm.graph[i].push_back(j);
        }
    }

    int ret = bm.solve();

    printf("%d\n", (int)(ret + (vt[0].size() - ret) / 2 * 2 + (vt[1].size() - ret) / 2 * 2 + (vt[0].size() - ret) % 2 * 3));
}



Measured memory_bytes: 18944