#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1000000007;
constexpr long long INF = 1LL << 60;
constexpr long double EPS = 1e-10;
void divisor_prime(long long n, vector<pair<long long, long long> >& ret) {
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back({i, 0});
      while (n % i == 0) {
        n /= i;
        ret[ret.size() - 1].second++;
      }
    }
  }
  if (n != 1) ret.push_back({n, 1});
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  vector<long long> k(n);
  for (int(i) = (int)(0); i < (int)(n); i++) cin >> k[i];
  long long ans = 0;
  sort((k).begin(), (k).end());
  vector<long long> prime;
  map<long long, long long> p_num;
  for (int(i) = (int)(2); i < (int)(5500); i++) {
    long long flag = 1;
    for (int(j) = (int)(0); j < (int)(prime.size()); j++) {
      if (i % prime[j] == 0) flag = 0;
      if (prime[j] * prime[j] > i) break;
    }
    if (flag) prime.push_back(i), p_num[prime.back()] = prime.size() - 1;
  }
  vector<long long> sum(5001, 0);
  vector<vector<long long> > prime_sum(5001,
                                       vector<long long>(prime.size(), 0));
  for (int(i) = (int)(1); i < (int)(5001); i++) {
    vector<pair<long long, long long> > ret;
    divisor_prime(i, ret);
    for (auto itr : ret)
      sum[i] += itr.second, prime_sum[i][p_num[itr.first]] += itr.second;
    sum[i] += sum[i - 1];
    for (int(j) = (int)(0); j < (int)(prime.size()); j++)
      prime_sum[i][j] += prime_sum[i - 1][j];
  }
  for (int(i) = (int)(0); i < (int)(n); i++) {
    ans += sum[k[i]];
  }
  long long l = 0, r = 0;
  long long mx = 0;
  for (int(i) = (int)(0); i < (int)(n); i++) {
    if (k[i] == 1)
      l = i + 1, r = i + 1;
    else if (k[i] >= prime[mx + 1]) {
      if ((r - l) * 2 > n) break;
      l = i, r = i + 1;
      while (k[i] >= prime[mx + 1]) mx++;
    } else
      r++;
  }
  if ((r - l) * 2 <= n) {
    cout << ans << endl;
    return 0;
  }
  long long dif = r - l - (n - r + l);
  for (int i = mx; i >= 0; i--) {
    long long lk = k[l], rk = k[r - 1];
    if ((r - l) * 2 <= n) break;
    dif = r - l - (n - r + l);
    if (prime_sum[lk][i] == prime_sum[rk][i]) {
      ans -= prime_sum[lk][i] * dif;
    } else {
      ans -= prime_sum[lk][i] * dif;
      long long d = prime_sum[lk][i];
      long long lt = l, rt = r;
      while (true) {
        lt++;
        if ((rt - lt) * 2 <= n) break;
        long long dift = rt - lt - (n - rt + lt);
        if (prime_sum[k[lt]][i] > d) {
          ans -= (prime_sum[k[lt]][i] - d) * dift;
          d = prime_sum[k[lt]][i];
        }
      }
      long long cnt = 1;
      for (int(j) = (int)(l + 1); j < (int)(r); j++) {
        if (prime_sum[k[j]][i] == prime_sum[k[j - 1]][i])
          cnt++;
        else {
          if (cnt * 2 > n) {
            r = j;
            l = r - cnt;
            break;
          } else
            cnt = 1;
        }
      }
      if (cnt * 2 > n)
        l = r - cnt;
      else
        break;
    }
  }
  cout << ans << "\n";
  return 0;
}
