#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

void findPrime(int N, vector<bool>& isPrime)
{
    isPrime.assign(N+1, true);
    isPrime[0] = isPrime[1] = false;
    for(int i=2; i*i<=N; i++){
        if(isPrime[i]){
            for(int j=i; i*j<=N; j++){
                isPrime[i*j] = false;
            }
        }
    }
}

int bipartiteMaximumMatchings(const vector<vector<bool> >& graph)
{
    int ret = 0;
    int n = graph.size();
    if(n == 0)
        return 0;
    int m = graph[0].size();
    if(m == 0)
        return 0;
    vector<int> selectN(n, -1);
    vector<int> selectM(m, -1);

    for(int i=0; i<n; ++i){
        vector<bool> visitedN(n, false);
        vector<bool> visitedM(m, false);
        visitedN[i] = true;
        vector<int> path(min(n,m)*2, -1);

        path[0] = i;
        int index = 1;
        for(;;){
            while(++path[index] < m && (!graph[path[index-1]][path[index]] || selectN[path[index-1]]==path[index] || visitedM[path[index]]));
            if(path[index] < m){
                if(selectM[path[index]] == -1){
                    for(int j=0; j<index; j+=2){
                        selectN[path[j]] = path[j+1];
                        selectM[path[j+1]] = path[j];
                    }
                    ++ ret;
                    break;
                }
                if(!visitedN[selectM[path[index]]]){
                    path[index+1] = selectM[path[index]];
                    visitedM[path[index]] = true;
                    visitedN[path[index+1]] = true;
                    index += 2;
                }
            }
            else{
                path[index] = -1;
                index -= 2;
                if(index < 0)
                    break;
            }
        }

        if(ret == m)
            break;
    }

    return ret;
}

const int MAX = 10000000;

int main()
{
    vector<bool> isPrime;
    findPrime(MAX, isPrime);

    int n;
    cin >> n;
    set<int> s;
    for(int i=0; i<n; ++i){
        int x;
        cin >> x;
        for(int j=0; j<2; ++j){
            int y = x + j;
            if(s.find(y) == s.end())
                s.insert(y);
            else
                s.erase(y);
        }
    }

    vector<vector<int> > v(2);
    for(int x : s)
        v[x%2].push_back(x);

    int a = v[0].size();
    int b = v[1].size();
    vector<vector<bool> > graph(a, vector<bool>(b, false));
    for(int i=0; i<a; ++i){
        for(int j=0; j<b; ++j){
            int a = abs(v[0][i] - v[1][j]);
            if(a >= 3 && isPrime[a])
                graph[i][j] = true;
        }
    }

    int match = bipartiteMaximumMatchings(graph);
    int ans = match + ((a - match) / 2 + (b - match) / 2) * 2 + ((a - match) % 2) * 3;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1664