//  M. Triangle Construction

#include<bits/stdc++.h>

using namespace std;

const int N = 2e7 + 5;
bool p[N];
const int M = 755;
int match[M];
vector<int> G[M];
vector<int> l, r;
bool vis[M];
bool dfs(int u) {
    for (int v: G[u]) {
        if (!vis[v]) {
            vis[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {

    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> a(n);
    int cnt1 = 0;

    for (int i = 2; i < N; i++) {
        if (!p[i]) {
            for (int j = 2; j * i < N; j++) {
                p[i * j] = true;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] == 1) {
            cnt1++;
            if (cnt1 == 1) {
                l.push_back(a[i]);
            }
        } else if (a[i] % 2 == 1) {
            l.push_back(a[i]);
        } else {
            r.push_back(a[i]);
        }
    }

    for (int i = 0; i < l.size(); i++) {
        int p1 = l[i];
        for (int j = 0; j < r.size(); j++) {
            int p2 = r[j];
            if (!p[p1 + p2]) {
              //  cout <<" from " << i <<" to " << j << endl;
                G[i].push_back(j);
            }
        }
    }
    int cnt = 0;
    memset(match,-1,sizeof(match));
    for (int i = 0; i < l.size(); i++) {
       // cout <<" check " << i << endl;
        memset(vis,0,sizeof(vis));
        if (dfs(i)) {
            cnt++;
           // cout <<" match " << i <<"->" << match[i] << endl;
        }
    }
   // cout <<" cnt is " << cnt << endl;

    cout << (r.size() + l.size() - cnt);


    return 0;
}