#include <bits/stdc++.h>
using namespace std;
int n;
long long F[10][100];
int total[10], putere[10][100], G[10][10], C[10], gr[10], D[10][1 << 8];
map<long long, int> M[10], now;
inline void descompune(long long n, const int &indice) {
  for (int f = 2; 1LL * f * f <= n; ++f) {
    if (n % f == 0) {
      F[indice][++putere[indice][0]] = f;
      while (n % f == 0) {
        ++putere[indice][putere[indice][0]];
        n /= f;
        ++total[indice];
      }
      M[indice][f] = putere[indice][putere[indice][0]];
    }
  }
  if (n > 1) {
    F[indice][++putere[indice][0]] = n;
    putere[indice][putere[indice][0]] = 1;
    M[indice][n] = 1;
    ++total[indice];
  }
}
inline bool includes(const int &i, const int &j) {
  for (map<long long, int>::iterator itt = M[j].begin(); itt != M[j].end();
       ++itt) {
    long long f = itt->first;
    int p = itt->second;
    if (M[i][f] < p) return 0;
  }
  return 1;
}
inline void sortare() {
  int p = 1, u = 0;
  for (int i = 1; i <= n; ++i) {
    if (!gr[i]) {
      C[++u] = i;
    }
  }
  while (p <= u) {
    int nod = C[p];
    for (int i = 1; i <= G[nod][0]; ++i) {
      int vecin = G[nod][i];
      --gr[vecin];
      if (!gr[vecin]) {
        C[++u] = vecin;
      }
    }
    ++p;
  }
}
int main() {
  scanf("%d", &n);
  long long x;
  int sol = 0;
  for (int i = 1; i <= n; ++i) {
    scanf("%I64d", &x);
    descompune(x, i);
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (i == j) continue;
      if (includes(i, j)) {
        G[j][++G[j][0]] = i;
        ++gr[i];
      }
    }
  }
  sortare();
  for (int i = 1; i <= n; ++i) {
    for (int conf = 0; conf < (1 << n); ++conf) {
      D[i][conf] = 1000000009;
    }
  }
  D[1][1] = total[C[1]];
  if (total[C[1]] > 1) ++D[1][1];
  D[1][0] = 1000000009;
  for (int i = 2; i <= n; ++i) {
    for (int conf = 1; conf < (1 << i); ++conf) {
      D[i][conf] = 1000000009;
      if ((conf & (1 << (i - 1))) == 0) {
        continue;
      }
      D[i][conf] =
          D[i - 1][conf ^ (1 << (i - 1))] + total[C[i]] + (total[C[i]] != 1);
      for (int prev_conf = 1; prev_conf < (1 << (i - 1)); ++prev_conf) {
        int stop = 0;
        for (int b = 0; b < i - 1; ++b) {
          if (((conf & (1 << b)) != 0) && ((prev_conf & (1 << b)) == 0)) {
            stop = 1;
            break;
          }
        }
        if (stop) continue;
        now.clear();
        int tot = 0;
        stop = 0;
        for (int b = 0; b < i - 1; ++b) {
          if (((conf & (1 << b)) == 0) && ((prev_conf & (1 << b)) != 0)) {
            for (map<long long, int>::iterator itt = M[C[b + 1]].begin();
                 itt != M[C[b + 1]].end() && !stop; ++itt) {
              long long f = itt->first;
              int p = itt->second;
              now[f] += p;
              tot += p;
              if (now[f] > M[C[i]][f]) {
                stop = 1;
              }
            }
            if (stop) {
              break;
            }
          }
        }
        if (!stop) {
          D[i][conf] =
              min(D[i][conf], D[i - 1][prev_conf] + total[C[i]] - tot + 1);
        }
      }
    }
  }
  sol = 1000000009;
  for (int conf = 1; conf < (1 << n); ++conf) {
    sol = min(sol, D[n][conf] + 1);
  }
  sol = min(sol, D[n][(1 << (n - 1))]);
  printf("%d\n", sol);
  return 0;
}
