#include <bits/stdc++.h>
bool u[1000001];
int pr[500001];
int l;
int n;
long long a[8];
int f[7000];
int thr[10];
int b[8];
int inf = 10000;
int g[8];
int cal(long long x) {
  int i;
  int ret = 0;
  for (i = 1; i <= l && pr[i] <= x / pr[i]; i++) {
    while (x % pr[i] == 0) {
      x = x / pr[i];
      ret++;
    }
  }
  if (x > 1) ret++;
  return ret;
}
void dfs(int x, int y, long long z, int r, int cur) {
  int i;
  if (r == n) {
    if (f[x] > f[y] + cur + 1) f[x] = f[y] + cur + 1;
  } else {
    if (z % a[r] == 0 && b[r] == 2)
      dfs(x, y - thr[r], z / a[r], r + 1, cur - g[r]);
    dfs(x, y, z, r + 1, cur);
  }
}
int main() {
  int i, j;
  memset(u, true, sizeof(u));
  l = 0;
  for (i = 2; i <= 1000000; i++) {
    if (u[i]) {
      l++;
      pr[l] = i;
    }
    for (j = 1; j <= l && i <= 1000000 / pr[j]; j++) {
      u[i * pr[j]] = false;
      if (i % pr[j] == 0) break;
    }
  }
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%I64d", &a[i]);
  for (i = 0; i < n; i++) g[i] = cal(a[i]);
  thr[0] = 1;
  for (i = 1; i <= n; i++) thr[i] = thr[i - 1] * 3;
  int mm = inf;
  f[0] = 0;
  for (i = 1; i < thr[n] - 1; i++) {
    int cur = i;
    bool flag = true;
    for (j = n - 1; j >= 0; j--) {
      b[j] = cur / thr[j];
      cur = cur % thr[j];
      if (b[j] == 0) flag = false;
    }
    f[i] = inf;
    for (j = 0; j < n; j++)
      if (b[j] == 1) {
        if (g[j] == 1) {
          if (f[i] > f[i - thr[j]] + 1) f[i] = f[i - thr[j]] + 1;
        } else {
          if (f[i] > g[j] + f[i - thr[j]] + 1) f[i] = g[j] + f[i - thr[j]] + 1;
        }
        dfs(i, i - thr[j], a[j], 0, g[j]);
      }
    if (flag) {
      for (j = 0; j < n; j++)
        if (b[j] == 1) break;
      if (i + thr[j] == thr[n] - 1) {
        if (f[i] < mm) mm = f[i];
      } else {
        if (f[i] + 1 < mm) mm = f[i] + 1;
      }
    }
  }
  printf("%d\n", mm);
  return 0;
}
