#include <iostream>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>
#include <queue>
#include <sstream>
#include <ctime>
#include <iterator>
#include <string.h>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <fstream>
#include <assert.h>
#include <numeric>
#include <complex>
#include <random>
#include <utility>



#define IOS ios_base::sync_with_stdio(0),cin.tie(0), cout.tie(0);
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a) - 1; i>=(b);i--)
#define rep(i,n) FOR(i,0,n)
#define PB push_back
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define VI vector<int>
#define PII pair<int,int>
#define PLL pair<long long,long long>
#define VL vector<long long >
#define FILL(a, value) memset(a, value, sizeof(a))
const int nax = 2 * (int)1e5 + 147;
 
using namespace std;
 
const int MOD = 998244353;
const int INF = 1e9 +47 ;
const long long LINF = (long long)1e18 + 4747;
 
typedef long long LL;
const double EPS=1e-6;

int p[(int)1e7 * 2 + 4];
int cc[770 * 770];
vector<int > g[770];
vector<int> mt;
vector<bool> used;
bool try_kuhn(int v) {
    if (used[v])
        return false;
    used[v] = true;
    for (int to : g[v]) {
        if (mt[to] == -1 || try_kuhn(mt[to])) {
            mt[to] = v;
            return true;
        }
    }
    return false;
}

int main() {
    int m;
    cin >> m;
    vector<int> b(m);
    for(int i = 0;i < m;i ++ )
    {
        cin >> b[i];
        
    }
    sort(b.begin(),b.end());
    int id = 0;
    while(id < m && b[id] ==1)id++;
    if(id!=0)id--;
    int del = id;
    int n = m - id;
    vector<int> par;
    vector<int> nepar;
    while(id != m) {
        if(b[id] % 2 == 0)par.push_back(b[id]);
        else nepar.push_back(b[id]);
        id++;
    }
    for(int i = 0; i <=1e7 * 2;i ++ )p[i] = true;
    p[0] = p[1] = false;
    int mx =(int)1e7;
    for (int i = 2; i * i <= mx; i++) {
        if(p[i]) {
            for (int j = i * i; j <= mx; j += i) {
                p[j] = false;
            }
        }
    }
    n = par.size();
    int k = nepar.size();
    for(int i = 0;i < par.size();i ++ ) {
        for(int j = 0; j < nepar.size(); j++) {
            if(p[par[i] + nepar[j]]) {
           //     cout << i << ' ' << j << '\n';
                g[i].push_back(j);
            }
        }
    }
     mt.assign(k, -1);
       for (int v = 0; v < n; ++v) {
           used.assign(n, false);
           try_kuhn(v);
       }
    int ans = 0;
    for(int i = 0;i <k;i ++) {
        if(mt[i]!=-1)ans++;
    }
    cout << m - del -  ans << '\n';
    
}