#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];
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0;i < n;i ++ )
    {
        cin >> a[i];
    }
    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;
            }
        }
    }
    for(int i = 0;i <n;i ++ )
    {
        for(int j = i + 1;j < n;j ++ ) {
            if(p[a[i] + a[j]] == true) {
                cc[i]++;
                cc[j]++;
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    set<pair<int,int>>s;
    for(int i = 0;i < n;i ++) {
        s.insert({cc[i],i});
    }
    int ans = 0;
    while(!s.empty() && s.rbegin()->first > 0) {
        auto v= *s.rbegin();
        s.erase(*s.rbegin());
        ans++;
        for(auto x : g[v.second]) {
            if(s.count({cc[x],x})) {
                s.erase({cc[x],x});
                cc[x]--;
                s.insert({cc[x],x});
            }
        }
    }
    cout << n - ans << '\n';
    
}