#include <bits/stdc++.h>
using namespace std;
int const m = 5000;
int val[5005], tree[5005], p[5005], cnt, id[5005], minfac[5005], siz[10005],
    fa[10005], len[10005], target[20005], pre[20005], last[10005], tot,
    w[20005], siz2[10005], mx[10005];
bool flag[5005];
long long res;
void add(int x, int y) {
  for (int i = x; i; i -= (i & (-i))) tree[i] += y;
}
int ask(int x) {
  int res = 0;
  for (int i = x; i <= m; i += (i & (-i))) res += tree[i];
  return res;
}
void add(int x, int y, int z) {
  target[++tot] = y;
  pre[tot] = last[x];
  last[x] = tot;
  w[tot] = z;
}
void dfs(int x, int fa) {
  siz2[x] = siz[x];
  for (int i = last[x]; i; i = pre[i]) {
    int tar = target[i];
    if (tar == fa) continue;
    dfs(tar, x);
    mx[x] = max(mx[x], siz2[tar]);
    siz2[x] += siz2[tar];
  }
}
void dfs2(int x, int fa) {
  siz2[x] = siz[x];
  for (int i = last[x]; i; i = pre[i]) {
    int tar = target[i];
    if (tar == fa) continue;
    dfs2(tar, x);
    res += 1ll * siz2[tar] * w[i];
    siz2[x] += siz2[tar];
  }
}
int main() {
  int n, x;
  scanf("%d", &n);
  while (n--) scanf("%d", &x), val[x]++;
  for (int i = 2; i <= m; i++) {
    if (!flag[i]) {
      p[++cnt] = i;
      id[i] = cnt;
      minfac[i] = i;
    }
    for (int j = 1; j <= cnt && i * p[j] <= m; j++) {
      flag[i * p[j]] = 1;
      minfac[i * p[j]] = p[j];
      if (!(i % p[j])) break;
    }
  }
  int sum = 1, facsum = 0;
  siz[1] = val[0] + val[1];
  for (int i = 2; i <= m; i++) {
    if (!flag[i]) {
      fa[++sum] = 1;
      siz[sum] = val[i];
      len[sum] = ++facsum;
      add(i, 1);
      continue;
    }
    int v = i, cnt = 1;
    while (flag[v]) v /= minfac[v], cnt++;
    int t = ask(v), lef = facsum - t, tmp = sum;
    while (len[tmp] <= lef) lef -= len[tmp], tmp = fa[tmp];
    if (!lef) {
      fa[++sum] = tmp;
      facsum += cnt;
      len[sum] = facsum - t;
      siz[sum] = val[i];
    } else {
      fa[++sum] = fa[tmp];
      len[sum] = len[tmp] - lef;
      len[tmp] = lef;
      fa[tmp] = sum;
      sum++;
      fa[sum] = sum - 1;
      facsum += cnt;
      len[sum] = facsum - t;
      siz[sum] = val[i];
    }
    v = i;
    while (flag[v]) add(minfac[v], 1), v /= minfac[v];
    add(v, 1);
  }
  for (int i = 2; i <= sum; i++) add(fa[i], i, len[i]), add(i, fa[i], len[i]);
  dfs(1, 0);
  int root = 1;
  for (int i = 2; i <= sum; i++)
    if (max(mx[i], siz2[1] - siz2[i]) < max(mx[root], siz2[1] - siz2[root]))
      root = i;
  dfs2(root, 0);
  printf("%lld", res);
  return 0;
}
