#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
int b[5005], cnt, pr[800], f[800][5001], n, at[5005], sum[800][5001];
long long ans;
int ss[5005], tmp[5005], sa, st;
int main() {
  for (int i = 2; i <= 5000; i++) {
    if (b[i]) continue;
    for (int j = 2; j * i <= 5000; j++) b[i * j] = 1;
  }
  for (int i = 2; i <= 5000; i++)
    if (b[i] == 0) pr[++cnt] = i;
  for (int i = 1; i <= cnt; i++) {
    for (int j = 1; j <= 5000; j++) {
      if (j >= pr[i]) f[i][j] = j / pr[i] + f[i][j / pr[i]];
      sum[i][j] = sum[i - 1][j] + f[i][j];
    }
  }
  scanf("%d", &n);
  for (int i = 1, x; i <= n; i++) {
    scanf("%d", &x);
    if (x == 0) x = 1;
    ++at[x];
    ans += sum[cnt][x];
  }
  for (int i = 1; i <= 5000; i++)
    if (at[i]) ss[++sa] = i;
  for (int i = cnt; i >= 1;) {
    int s = 0, minn = 0x7fffffff;
    st = 0;
    for (int j = 1, a; j <= sa; j++) {
      a = ss[j];
      if (f[i][a]) s += at[a], minn = min(minn, f[i][a]);
    }
    if (s > n - s) {
      ans -= 1ll * minn * (s - n + s);
      for (int j = 1, a; j <= sa; j++) {
        a = ss[j];
        if (f[i][a]) f[i][a] -= minn, tmp[++st] = a;
      }
      for (int i = 1; i <= st; i++) ss[i] = tmp[i];
      sa = st;
    } else if (n - s > s) {
      for (int j = 1, a; j <= sa; j++) {
        a = ss[j];
        if (!f[i][a]) tmp[++st] = a;
      }
      for (int i = 1; i <= st; i++) ss[i] = tmp[i];
      sa = st;
      --i;
    } else {
      break;
    }
  }
  printf("%lld", ans);
  return 0;
}
