#include <bits/stdc++.h>
using ll = long long;
const int C = 5003, D = 1001, E = 11, F = 16;
void supfactor(int* pr, int v) {
  int i, j;
  pr[1] = 1;
  for (i = 2; i * i < v; i++) {
    if (pr[i] == 0) {
      for (j = i; j < v; j += i) {
        if (pr[j] == 0) pr[j] = i;
      }
    }
  }
  for (; i < v; i++)
    if (pr[i] == 0) pr[i] = i;
}
int find_divs(int* pr, int a, int dv[], int s[]) {
  int ln = 0;
  while (a > 1) {
    if (ln == 0 || pr[a] != dv[ln - 1])
      dv[ln] = pr[a], s[ln] = 1, ln++;
    else
      s[ln - 1]++;
    a /= pr[a];
  }
  return ln;
}
int lg2[C];
void formulate_rmq(ll rmq[][C], ll vals[], int ln, int layers) {
  int i, j, s = 1;
  for (i = 0; i < ln; i++) lg2[i] = ((i > 1) ? (lg2[i / 2] + 1) : 0);
  for (i = 0; i < ln; i++) rmq[0][i] = vals[i];
  for (j = 1; j < layers; j++) {
    for (i = 0; i < ln; i++) {
      if (i + s < ln)
        rmq[j][i] =
            (((rmq[j - 1][i]) < (rmq[j - 1][i + s])) ? (rmq[j - 1][i])
                                                     : (rmq[j - 1][i + s]));
      else
        rmq[j][i] = rmq[j - 1][i];
    }
    s = s * 2;
  }
}
ll rmq[F][C];
ll rmq_query(int a, int b) {
  int x = lg2[b - a];
  return (((rmq[x][a]) < (rmq[x][b - (1 << x) + 1]))
              ? (rmq[x][a])
              : (rmq[x][b - (1 << x) + 1]));
}
ll points[C];
ll amount[C][D], value[C], sum_all[C];
int counter[C], pr[C], dv[E], s[E];
int main() {
  int n, a, i, j, ln, lstcnt = 0;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &a), points[a]++;
  supfactor(pr, C);
  for (i = 2; i < C; i++) {
    if (pr[i] == i) counter[i] = lstcnt++;
  }
  for (i = 2; i < C; i++) {
    ln = find_divs(pr, i, dv, s);
    for (j = 0; j < ln; j++) amount[i][counter[dv[j]]] = s[j];
    for (j = 0; j < D; j++) {
      amount[i][j] += amount[i - 1][j];
      sum_all[i] += amount[i][j];
      if (j >= counter[dv[ln - 1]]) value[i] += amount[i - 1][j];
    }
  }
  formulate_rmq(rmq, value, C, F);
  int lft = 0, rgt = 0, num_points = points[0], point_mx = 0;
  ll cur_mx = 0, res = 0;
  while (rgt < C - 1) {
    if (num_points * 2 < n)
      rgt += 1, num_points += points[rgt];
    else {
      if (lft + 1 <= rgt && rmq_query(lft + 1, rgt) > cur_mx)
        cur_mx = rmq_query(lft + 1, rgt), point_mx = rgt;
      else if (lft + 1 > rgt && sum_all[rgt] > cur_mx)
        cur_mx = sum_all[rgt], point_mx = rgt;
      num_points -= points[lft];
      lft++;
      if (lft > rgt) rgt++, num_points += points[rgt];
    }
  }
  for (i = 0; i < point_mx; i++)
    res += (sum_all[i] + cur_mx -
            2 * (((rmq_query(i + 1, point_mx)) < (cur_mx))
                     ? (rmq_query(i + 1, point_mx))
                     : (cur_mx))) *
           points[i];
  res += (sum_all[point_mx] + cur_mx -
          2 * (((sum_all[point_mx]) < (cur_mx)) ? (sum_all[point_mx])
                                                : (cur_mx))) *
         points[point_mx];
  for (i = point_mx + 1; i < C - 1; i++)
    res += (sum_all[i] + cur_mx -
            2 * (((rmq_query(point_mx + 1, i)) < (cur_mx))
                     ? (rmq_query(point_mx + 1, i))
                     : (cur_mx))) *
           points[i];
  printf("%lld\n", res);
  return 0;
}
