#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 10;
pair<int, map<long long, int> > dp[2][1 << 8];
const int inf = 0x3f3f3f3f;
vector<int> vc[10];
int n;
inline int lowbit(int x) { return x & -x; }
pair<int, map<long long, int> > cal(pair<int, map<long long, int> > x,
                                    pair<int, map<long long, int> > y,
                                    bool can) {
  map<long long, int> tmp;
  pair<int, map<long long, int> > res = make_pair(inf, tmp);
  map<long long, int> mp1 = x.second;
  map<long long, int> mp2 = y.second;
  tmp = mp1;
  if (can)
    for (__typeof((mp2).begin()) it2 = (mp2).begin(); it2 != (mp2).end();
         ++it2) {
      if (mp1.find(it2->first) == mp1.end() || mp1[it2->first] < it2->second) {
        can = false;
        return res;
      }
    }
  if (can) {
    int add = 0;
    for (__typeof((mp1).begin()) it1 = (mp1).begin(); it1 != (mp1).end(); ++it1)
      add += it1->second - mp2[it1->first];
    res = make_pair(y.first + add + 1, tmp);
  } else {
    for (__typeof((mp2).begin()) it2 = (mp2).begin(); it2 != (mp2).end();
         ++it2) {
      tmp[it2->first] += it2->second;
    }
    res = make_pair(x.first + y.first, tmp);
  }
  return res;
}
inline void update(pair<int, map<long long, int> >& x,
                   const pair<int, map<long long, int> >& y) {
  if (y.first < x.first) x = y;
}
int main() {
  while (cin >> n) {
    map<long long, int> tmp;
    for (int i = 0; i < ((1) << (n)); ++i) {
      dp[0][i] = make_pair(inf, tmp);
      dp[1][i] = make_pair(inf, tmp);
    }
    for (int i = 0; i < n; ++i) {
      vc[i].clear();
      long long x;
      cin >> x;
      tmp.clear();
      int tot = 0;
      for (int j = 2; j <= 1000000 && 1LL * j * j <= x; ++j) {
        if (x % j == 0) {
          long long t = j;
          int cnt = 0;
          while (x % j == 0) {
            x /= j;
            ++cnt;
            ++tot;
          }
          tmp[t] = cnt;
        }
      }
      if (x > 1) {
        tmp[x] = 1;
        ++tot;
      }
      dp[0][((1) << (i))] = dp[1][((1) << (i))] =
          make_pair(tot == 1 ? 1 : (tot + 1), tmp);
    }
    tmp.clear();
    dp[0][0] = make_pair(0, tmp);
    dp[1][0] = make_pair(0, tmp);
    for (int i = 1; i < ((1) << (n)); ++i) {
      for (int j = i; j; j -= lowbit(j)) {
        int p = lowbit(j), q = p ^ i;
        if (q == 0) continue;
        pair<int, map<long long, int> > now = cal(dp[0][p], dp[0][q], true);
        update(dp[0][i], now);
        update(dp[1][i], now);
        now = cal(dp[0][p], dp[1][q], true);
        update(dp[0][i], now);
        update(dp[1][i], now);
      }
      for (int j = (i - 1) & i; j; j = (j - 1) & i) {
        int k = j ^ i;
        if (k == 0) continue;
        pair<int, map<long long, int> > now = cal(dp[1][j], dp[1][k], false);
        update(dp[1][i], now);
        now.first++;
        update(dp[0][i], now);
      }
    }
    cout << dp[0][((1) << (n)) - 1].first << endl;
  }
  return 0;
}
