#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
ll ar[1000009], n, inp[(ll)(5e3 + 4)], cc = 0, cnt[(ll)(5e3 + 4)], nn;
vector<pair<ll, ll>> pr[(ll)(5e3 + 4)];
vector<ll> pri;
vector<vector<pair<ll, ll>>> vvp;
bool ch[(ll)(5e3 + 4)];
void sieve() {
  for (ll i = 2; i < (ll)(5e3 + 4); i++) {
    if (!ch[i]) {
      pri.push_back(i);
      inp[i] = cc++;
      for (ll j = i; j < (ll)(5e3 + 4); j += i) {
        ll xx = j, cc = 0;
        while (xx % i == 0) {
          cc++;
          xx /= i;
        }
        pr[j].push_back(make_pair(i, cc));
        ch[j] = 1;
      }
    }
  }
}
ll ans(ll i, ll j) {
  if (i > j) {
    return 0;
  }
  if (vvp[ar[j] - 2].size() == 0) {
    return 0;
  }
  vector<pair<ll, ll>> vp;
  vector<ll> count;
  ll ss = vvp[ar[j] - 2].size(), pe = j, co = cnt[ar[j]], ma = 0,
     mco = cnt[ar[j]];
  for (ll x = j - 1; x >= i - 1; x--) {
    if (x == i - 1 || vvp[ar[x] - 2].size() != ss) {
      if (co > mco) {
        ma = vp.size();
        mco = co;
      }
      vp.push_back(make_pair(x + 1, pe));
      pe = x;
      if (x >= i) {
        co = cnt[ar[x]];
        ss = vvp[ar[x] - 2].size();
      }
    } else {
      co += cnt[ar[x]];
    }
  }
  if (mco * 2 <= n) {
    return 0;
  }
  ll d = vvp[ar[vp[ma].first] - 2].back().second;
  for (ll x = vp[ma].first; x <= vp[ma].second; x++) {
    if ((vvp[ar[x] - 2].back().second -= d) == 0) {
      vvp[ar[x] - 2].pop_back();
    }
  }
  return (d * (2 * mco - n) + ans(vp[ma].first, vp[ma].second));
}
int main() {
  cin >> n;
  ll ma = 0;
  for (ll i = 0; i < n; i++) {
    cin >> ar[i];
    cnt[ar[i]]++;
    ma = max(ar[i], ma);
  }
  sort(ar, ar + n);
  nn = unique(ar, ar + n) - ar;
  sieve();
  vector<pair<ll, ll>> vp;
  ll ii = 0;
  for (ll i = 2; i <= ma; i++) {
    if (ii + 1 < pri.size() && pri[ii + 1] <= i) {
      ii++;
    }
    for (auto x : pr[i]) {
      if (inp[x.first] == vp.size()) {
        vp.push_back(x);
      } else {
        vp[inp[x.first]].second += x.second;
      }
    }
    vvp.push_back(vp);
  }
  ll an = 0, st = 0;
  for (ll i = 0; i < nn; i++) {
    if (ar[i] <= 1) {
      st++;
      continue;
    }
    for (auto x : vvp[ar[i] - 2]) {
      an += cnt[ar[i]] * x.second;
    }
  }
  cout << an - ans(st, nn - 1) << "\n";
}
