#include <bits/stdc++.h>
using namespace std;
const int N = 1234567;
const int INF = 10000000;
int prime[N / 10], top = 0;
bool f[N];
void get_prime() {
  f[1] = 1;
  for (int i = 2; i < N; i++) {
    if (!f[i]) prime[top++] = i;
    for (int j = 0; j < top && i * prime[j] < N; j++) {
      f[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
long long a[N];
int n;
int vis[1 << 9], FF[1 << 9];
int get_ans(long long n) {
  if (n == 1) return 0;
  long long m = n;
  int ret = 0;
  for (int i = 0; i < top && (long long)prime[i] * prime[i] <= n; i++) {
    int cnt = 0;
    while (n % prime[i] == 0) {
      n /= prime[i];
      cnt++;
    }
    ret += cnt;
  }
  if (m == n) return 1;
  if (n != 1) ret++;
  return ret + 1;
}
int is_prime(long long n) {
  if (n < N) {
    if (f[n])
      return 0;
    else
      return 1;
  }
  for (int i = 0; i < top && (long long)prime[i] * prime[i] <= n; i++)
    if (n % prime[i] == 0) return 0;
  return 1;
}
int deal(int tot) {
  if (vis[tot] != -1) return vis[tot];
  vector<long long> hh;
  hh.clear();
  int ans = 0;
  for (int i = 0; i < n; i++)
    if (tot & (1 << i)) {
      int find = 0;
      for (int j = 0; j < hh.size(); j++)
        if (hh[j] % a[i] == 0) {
          if (!is_prime(a[i])) ans++;
          hh.push_back(hh[j] / a[i]);
          hh[j] = a[i];
          find = 1;
          break;
        }
      if (!find) {
        if (hh.size() > 0) return vis[tot] = INF;
        ans += get_ans(a[i]);
        hh.push_back(a[i]);
      }
      sort(hh.begin(), hh.end());
    }
  return vis[tot] = ans;
}
int calc(int tot) {
  if (tot == 0) return 0;
  if (FF[tot] != -1) return FF[tot];
  int ret = INF;
  for (int i = tot; i != 0; i = (i - 1) & tot) {
    int tmp = calc(tot ^ i) + deal(i);
    if (tmp < ret) ret = tmp;
  }
  return FF[tot] = ret;
}
bool cmpr(long long i, long long j) { return i > j; }
int main() {
  get_prime();
  memset(vis, -1, sizeof(vis));
  memset(FF, -1, sizeof(FF));
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  sort(a, a + n, cmpr);
  n = unique(a, a + n) - a;
  int tot = (1 << n) - 1;
  int ans = deal(tot);
  for (int i = (tot - 1) & tot; i != 0; i = (i - 1) & tot) {
    int tmp = calc(tot ^ i) + deal(i) + 1;
    if (tmp < ans) ans = tmp;
  }
  cout << ans << endl;
  return 0;
}
