#include <bits/stdc++.h>
using namespace std;
const unsigned long long P = 239017, MaxN = 2100000, INF = 100000000;
int n, dp[10][4000], f[10], dp1[10][10000];
vector<int> p;
bool pr[1000001];
long long a[100];
int can(int k, int msk) {
  if (k == n) return 1;
  long long t = 1;
  for (int i = 0; i < n; ++i) {
    if ((1 << i) & msk) {
      t *= a[i];
      if (t <= 0 || t % a[i] != 0) return 0;
    }
  }
  return a[k] % t == 0;
}
int func(int k, int msk) {
  if (k == n) return 0;
  int ans = f[k];
  for (int i = 0; i < n; ++i)
    if ((1 << i) & msk) ans -= f[i];
  return ans;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%I64d", &a[i]);
  for (int i = 0; i <= 1000000; ++i) pr[i] = 1;
  pr[0] = pr[1] = 0;
  f[n] = -1;
  for (int i = 2; i <= 1000000; ++i) {
    if (!pr[i]) continue;
    if ((long long)i * (long long)i <= 1000000)
      for (int j = i * i; j <= 1000000; j += i) pr[j] = 0;
    p.push_back(i);
  }
  sort(a, a + n);
  for (int i = 0; i < n; ++i) {
    long long a1 = a[i];
    for (int j = 0; j < p.size(); ++j)
      while (a1 % p[j] == 0) a1 /= p[j], ++f[i];
    f[i] += a1 > 1;
  }
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j < 1 << (n + 1); ++j) dp[i][j] = INF;
  for (int i = 0; i < n; ++i) dp[i][1 << i] = f[i] == 1 ? 1 : f[i] + 1;
  for (int i = 0; i <= n; ++i) {
    for (int child = 0; child < 1 << i; ++child) {
      if (!can(i, child)) continue;
      for (int t = 0; t <= i; ++t)
        for (int j = 0; j < 1 << i; ++j) dp1[t][j] = INF;
      dp1[0][0] = 0;
      for (int now = 0; now < i; ++now) {
        for (int mask = 0; !((1 << now) & child) && mask < 1 << i; ++mask)
          dp1[now + 1][mask] = min(dp1[now + 1][mask], dp1[now][mask]);
        for (int mask = 0; ((1 << now) & child) && mask < 1 << i; ++mask) {
          for (int nw = 0; nw < 1 << now; ++nw) {
            int t = nw | (1 << now);
            dp1[now + 1][mask | t] =
                min(dp1[now + 1][mask | t], dp1[now][mask] + dp[now][t]);
          }
        }
      }
      for (int mask = 0; mask < 1 << i; ++mask)
        dp[i][mask | (1 << i)] =
            min(dp1[i][mask] + func(i, child) + 1, dp[i][mask | (1 << i)]);
    }
  }
  printf("%d\n", min(dp[n - 1][(1 << n) - 1], dp[n][(1 << (n + 1)) - 1]));
  return 0;
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j < 1 << (n + 1); ++j) {
      printf("root : %d - ( ", i);
      for (int t = 0; t <= n; ++t)
        if ((1 << t) & j) printf("%d ", t);
      printf(") : dp = %d\n", dp[i][j]);
    }
  return 0;
}
