#include <bits/stdc++.h>
#define rep(n) for(lint I = 0; (I) < (lint)(n); ++(I))
#define repeat(i, n) for(lint i = 0; (i) < (lint)(n); ++(i))
#define repeat_to(i, n) for(lint i = 0; (i) <= (lint)(n); ++(i))
#define repeat_from(i, m, n) for(lint i = (m); (i) < (lint)(n); ++(i))
#define repeat_from_to(i, m, n) for(lint i = (m); (i) <= (lint)(n); ++(i))
#define el cout<<endl
#define dump(x) cout<<" "<<#x<<"="<<x
#define vdump(v) for(size_t I=0; I<v.size(); ++I){cout<<" "<<#v<<"["<<I<<"]="<<v[I];} cout<<endl
using namespace std;
using lint = long long;
using ld = long double;

// 2部グラフの最大マッチング O(f(N+M)) f:=最大マッチング数で高々N
class bipartite_matching {
public:
    int n;
    vector<vector<int>> g;
    vector<int> match;

    bipartite_matching(int n_) : n(n_), g(n_), match(n_), used(n_) {}

    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int maximum_matching(void) {
        int res = 0;
        fill(begin(match), end(match), -1);
        for (int v = 0; v < n; ++v) {
            if (match[v] == -1) {
                fill(begin(used), end(used), false);
                if (dfs(v)) res++;
            }
        }
        return res;
    }

private:
    vector<int> used;
    bool dfs(int v) {
        used[v] = true;
        for (int u : g[v]) {
            int w = match[u];
            if (w == -1 || (!used[w] && dfs(w))) {
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
        return false;
    }
};

// エラトステネスの篩[2,n]を列挙 O(nloglogn)
vector<lint> sieve_of_eratosthenes(lint n) {
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (lint i = 2; i*i <= n; ++i)
        if (is_prime[i])
            for (lint k = i+i; k <= n; k += i)
                is_prime[k] = false;
    vector<lint> primes;
    for (lint i = 2; i <= n; ++i)
        if (is_prime[i])
            primes.push_back(i);
    return primes;
}

int main(void) {
    int n; cin >> n;
    
    vector<int> x, y_tag, y;
    rep(n) {
        int a; cin >> a;
        x.push_back(a);
    }
    
    repeat(i, n) {
        y_tag.push_back(x[i] - 1);
        y_tag.push_back(x[i]);
    }
    
    repeat(i, y_tag.size()) {
        if (count(y_tag.begin(), y_tag.end(), y_tag[i]) % 2 == 1) {
            y.push_back(y_tag[i]);
        }
    }
    sort(y.begin(), y.end());
    
    // 1 - 10^7+1 の奇素数リスト
    vector<lint> primes = sieve_of_eratosthenes(1e7 + 1);
    
    auto is_odd_prime = [&primes](const lint p) -> bool {
        assert(p > 0);
        if (p == 1) return false;
        if (p % 2 == 0) return false;
        if (!binary_search(primes.begin(), primes.end(), p)) return false;
        return true;
    };
    
    lint odds_num = 0, evens_num = 0;
    repeat(i, y.size()) {
        if (y[i] % 2 == 1) ++odds_num;
        else ++evens_num;
    }
    
    bipartite_matching bm(y.size());
    
    repeat(i, y.size()) {
        repeat_from(j, i + 1, y.size()) {
            lint d = y[j] - y[i];
            if (y[i] % 2 != y[j] % 2 && is_odd_prime(d)) {
                bm.add_edge(i, j);
            }
        }
    }
    
    lint matching_num = bm.maximum_matching();
    
    lint ans = matching_num;
    lint odds_remains = odds_num - matching_num;
    lint evens_remains = evens_num - matching_num;
    
    if ( odds_remains % 2 == 0) {
        ans += ((odds_remains) / 2) * 2;
        ans += ((evens_remains) / 2) * 2;
    }
    else {
        ans += ((odds_remains) / 2) * 2;
        ans += ((evens_remains) / 2) * 2;
        ans += 3;
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 11760