#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int f = 1, x = 0;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = -1LL;
  } while (ch < '0' || ch > '9');
  do {
    x = x * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  return f * x;
}
inline long long readll() {
  long long f = 1, x = 0;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = -1LL;
  } while (ch < '0' || ch > '9');
  do {
    x = x * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  return f * x;
}
template <class T>
inline void chmax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void chmin(T &a, T b) {
  if (a > b) a = b;
}
inline void swap(int &a, int &b) {
  int c = a;
  a = b;
  b = c;
}
using namespace std;
const int N = 5e3 + 10;
int n, cnt;
int pri[N][777], id[N], num[N];
inline void prewk() {
  for (int i = (2); i <= (N - 1); ++i) {
    std::copy(pri[i - 1] + 1, pri[i - 1] + cnt + 1, pri[i] + 1);
    int x = i;
    for (int j = (2); j <= (i - 1); ++j) {
      while (x % j == 0) {
        x /= j;
        ++pri[i][id[j]];
      }
    }
    if (x == i) {
      id[x] = ++cnt;
      ++pri[i][id[x]];
    }
  }
}
int ok[N];
int main() {
  prewk();
  n = read();
  for (int i = (1); i <= (n); ++i) ++num[read()];
  long long ans = 0;
  for (int i = (2); i <= (5000); ++i) {
    for (int j = (1); j <= (672); ++j) {
      ans += 1ll * num[i] * pri[i][j];
    }
  }
  int curcnt = n;
  for (int i = (1); i <= (5000); ++i) ok[i] = 1;
  while (curcnt > n / 2) {
    vector<int> prime(672);
    for (int i = (2); i <= (5000); ++i) {
      if (ok[i]) {
        for (int j = (672); j >= (1); --j) {
          if (pri[i][j]) {
            prime[j] += num[i];
            break;
          }
        }
      }
    }
    int best = max_element(prime.begin(), prime.end()) - prime.begin();
    vector<int> gd;
    for (int i = (2); i <= (5000); ++i) {
      if (ok[i]) {
        for (int j = (672); j >= (1); --j) {
          if (pri[i][j]) {
            if (j == best) --pri[i][j], gd.emplace_back(i);
            break;
          }
        }
      }
    }
    curcnt = 0;
    for (auto x : gd) curcnt += num[x];
    if (curcnt <= n / 2) break;
    for (int i = (1); i <= (5000); ++i) ok[i] = 0;
    for (auto x : gd) ok[x] = 1;
    ans -= curcnt;
    ans += (n - curcnt);
  }
  printf("%lld\n", ans);
  return 0;
}
