#include <bits/stdc++.h>
using namespace std;
const int MAXK = 5000;
const int PRIMESIZE = 669;
int n;
vector<int> prime;
map<int, int> primeIndex;
int number[MAXK + 1];
bool isPrime[MAXK + 1];
vector<int> factor[MAXK + 1];
vector<int> power[MAXK + 1];
long long int dist[MAXK + 1];
int fPower[MAXK + 1][PRIMESIZE];
int fPowerIndex[MAXK + 1];
void prep();
void fastIO();
void sieve();
void init();
void read();
long long int answer();
long long int getSum();
int nextPrime(int);
void popLargestFactor(int);
int main() {
  prep();
  read();
  cout << answer() << endl;
  return 0;
}
void prep() {
  fastIO();
  sieve();
  init();
}
void fastIO() {
  ios_base ::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
void sieve() {
  for (int n = 2; n <= MAXK; n++) isPrime[n] = true;
  int ind = 0;
  for (int n = 0; n <= MAXK; n++) {
    if (isPrime[n]) {
      prime.push_back(n);
      primeIndex[n] = ind++;
      int m = n;
      while (m <= MAXK) {
        factor[m].push_back(n);
        int c = 0;
        int k = m;
        while (k % n == 0) {
          k /= n;
          c++;
        }
        power[m].push_back(c);
        isPrime[m] = false;
        m += n;
      }
    }
  }
}
void init() {
  dist[0] = dist[1] = 0;
  fPowerIndex[0] = -1;
  fPowerIndex[1] = -1;
  for (int n = 2; n <= MAXK; n++) {
    dist[n] = dist[n - 1];
    fPowerIndex[n] = fPowerIndex[n - 1];
    for (int i = 0; i < PRIMESIZE; i++) fPower[n][i] = fPower[n - 1][i];
    for (int i = 0; i < power[n].size(); i++) {
      dist[n] += power[n][i];
      int p = factor[n][i];
      int ind = primeIndex[p];
      fPower[n][ind] += power[n][i];
      fPowerIndex[n] = max(ind, fPowerIndex[n]);
    }
  }
}
void read() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    number[k]++;
  }
}
long long int answer() {
  long long int sum = getSum();
  bool first = true;
  int l, r, cnt;
  int lastFactor;
  while (true) {
    if (first) {
      first = false;
      l = r = cnt = -1;
      for (int i = 0; i < prime.size(); i++) {
        int p = prime[i];
        int q = nextPrime(p);
        int c = 0;
        for (int j = p; j < q; j++) c += number[j];
        if (c > cnt) {
          l = p;
          r = q;
          lastFactor = i;
          cnt = c;
        }
      }
    } else {
      int cnt1, cnt2;
      cnt1 = cnt2 = 0;
      int mid = r;
      for (int i = l; i < r; i++) {
        if (fPower[i][lastFactor] > 0) {
          cnt2 += number[i];
          if (mid == r) mid = i;
        } else if (lastFactor > 0)
          cnt1 += number[i];
      }
      if (cnt2 > cnt1) {
        l = mid;
        cnt = cnt2;
      } else if (cnt1 > cnt2) {
        r = mid;
        cnt = cnt1;
        lastFactor--;
      } else
        break;
    }
    if (cnt * 2 <= n) break;
    sum -= cnt * 2 - n;
    for (int i = l; i < r; i++) popLargestFactor(i);
  }
  return sum;
}
long long int getSum() {
  long long int sum = 0;
  for (int n = 0; n <= MAXK; n++) sum += number[n] * dist[n];
  return sum;
}
int nextPrime(int p) {
  int ind = primeIndex[p] + 1;
  if (ind < prime.size())
    return prime[ind];
  else
    return MAXK + 1;
}
void popLargestFactor(int m) {
  if (fPower[m][fPowerIndex[m]] == 0) fPowerIndex[m]--;
  fPower[m][fPowerIndex[m]]--;
}
