#include <bits/stdc++.h>
using namespace std;
const int N = 5000, M = 1000;
int n, cnt[N + 9];
void into() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    ++cnt[x ? x : 1];
  }
}
int b[N + 9], pr[M + 9], cp;
int c[N + 9][M + 9];
void Sieve() {
  for (int i = 2; i <= N; ++i) {
    if (!b[i]) pr[++cp] = i, c[i][cp] = c[i][0] = 1;
    for (int j = 1; j <= cp && i * pr[j] <= N; ++j) {
      int t = i * pr[j];
      b[t] = 1;
      c[t][0] = c[i][0] + 1;
      for (int k = 1; k <= cp; ++k) c[t][k] = c[i][k];
      ++c[t][j];
      if (i % pr[j] == 0) break;
    }
  }
  for (int i = 1; i <= N; ++i)
    for (int j = 0; j <= cp; ++j) c[i][j] += c[i - 1][j];
}
int ht[M + 9];
int a[N + 9], ca;
int now[M + 9];
void Get_ht() {
  for (int i = 1; i <= N; ++i)
    if (cnt[i]) a[++ca] = i;
  for (int id = cp + 1, ct = 0; 2333;) {
    for (int i = 1; i <= cp; ++i) now[i] = 0;
    for (int i = 1; i <= ca; ++i) {
      int t = a[i];
      if (c[t][id] > ct)
        now[id] += cnt[t];
      else
        for (int j = id - 1; j >= 1; --j)
          if (c[t][j]) {
            now[j] += cnt[t];
            break;
          }
    }
    int p = 0;
    for (int i = 1; i <= cp; ++i)
      if (now[i] > n >> 1) {
        p = i;
        break;
      }
    if (!p) break;
    int lst = 0;
    for (int i = 1; i <= ca; ++i) {
      int t = a[i], tmp = 0;
      if (c[t][id] > ct)
        tmp = id;
      else
        for (int j = id - 1; j >= 1; --j)
          if (c[t][j]) {
            tmp = j;
            break;
          }
      if (tmp == p) a[++lst] = t;
    }
    ca = lst;
    ct = id == p ? ct + 1 : 1;
    ++ht[id = p];
    ++ht[0];
  }
}
long long ans;
void Get_ans() {
  for (int i = 1; i <= N; ++i) {
    if (!cnt[i]) continue;
    int sum = c[i][0] + ht[0];
    for (int j = cp; j >= 1; --j)
      if (c[i][j] ^ ht[j]) {
        ans += (long long)cnt[i] * (sum - 2 * min(c[i][j], ht[j]));
        break;
      } else
        sum -= c[i][j] + ht[j];
  }
}
void work() {
  Sieve();
  Get_ht();
  Get_ans();
}
void outo() { printf("%lld\n", ans); }
int main() {
  into();
  work();
  outo();
  return 0;
}
