#include <bits/stdc++.h>
const int inf = 1e9 + 7;
const int mod = 1e9 + 7;
const double PI = 3.1415926535898;
const double eps = 1e-8;
template <class T>
inline T read() {
  char ch;
  bool flag = 0;
  T x = 0;
  while (ch = getchar(), !isdigit(ch))
    if (ch == '-') flag = 1;
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
  return flag ? -x : x;
}
struct {
  inline operator long long() { return read<long long>(); }
  inline operator int() { return read<int>(); }
  inline operator bool() { return read<bool>(); }
  inline operator double() {
    double _tmp;
    return scanf("%lf", &_tmp), _tmp;
  }
  template <class T>
  inline void operator()(T &x) {
    x = *this;
  }
  template <class T, class... A>
  inline void operator()(T &x, A &...a) {
    x = *this, this->operator()(a...);
  }
} IN;
template <class T>
inline T abs(T x) {
  if (x < 0) x = -x;
  return x;
}
template <class T>
inline T max(T x, T y) {
  if (x < y) x = y;
  return x;
}
template <class T>
inline T min(T x, T y) {
  if (x > y) x = y;
  return x;
}
template <class T>
inline void swap(T &x, T &y) {
  x ^= y ^= x ^= y;
}
template <class T>
inline void chkmax(T &x, T y) {
  if (x < y) x = y;
}
template <class T>
inline void chkmin(T &x, T y) {
  if (x > y) x = y;
}
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline int dec(int x, int y) {
  x -= y;
  if (x < 0) x += mod;
  return x;
}
inline int add(int x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  return x;
}
inline void sub(int &x, int y) {
  x -= y;
  if (x < 0) x += mod;
}
inline void pls(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
inline int modpow(int x, int y, int res = 1) {
  if (y == -1) y = mod - 2;
  for (; y; y >>= 1, x = mul(x, x))
    if (y & 1) res = mul(res, x);
  return res;
}
const int N = 5e3 + 5;
const int L = 5e3;
long long ans = 0;
int n, _, dis[N], val[N], hep[N], point[N], tot[N][N];
std::vector<int> num, tmp;
inline void init() {
  for (int i = 2; i <= L; ++i) {
    int num = i;
    for (int j = 2; j <= num; ++j)
      while (num % j == 0) num /= j, ++tot[i][j];
    for (int j = 1; j <= L; ++j) dis[i] += (tot[i][j] += tot[i - 1][j]);
  }
}
inline void upd(int x) {
  while (!tot[x][point[x]]) --point[x];
  --tot[x][point[x]];
}
int main() {
  IN(n);
  for (int i = 1; i <= n; ++i) IN(_), ++val[_];
  init();
  for (int i = 2; i <= L; ++i) ans += 1ll * dis[i] * val[i];
  int dep = 0;
  for (int i = 2; i <= L; ++i) num.push_back(i), point[i] = L, upd(i);
  while (true) {
    for (int x : num) hep[point[x]] += val[x];
    for (int i = 2; i <= L; ++i)
      if (2 * hep[i] > n) {
        for (int x : num)
          if (dis[x] > dep + 1 && point[x] == i) tmp.push_back(x), upd(x);
        num = tmp, tmp.clear();
        ans += n - 2 * hep[i], memset((hep), 0, sizeof((hep)));
        goto _continue;
      }
    break;
  _continue:;
    ++dep;
  }
  printf("%lld\n", ans);
  return 0;
}
