#include <bits/stdc++.h>
using namespace std;
int criba[5001];
vector<int> primos, hijos;
long long int factorizacion[5001][700];
long long int cantidad[5001], numFactores[5001], ultimoPrimo[5001];
long long int n, maxN, k, costo, hijoMayor;
long long int ini, fin, maxx, cuenta, actual, hijo, s, e;
int centroide() {
  int tmpIni, tmpFin, pos = s;
  ini = s;
  fin = 0;
  maxx = 0;
  cuenta = 0;
  actual = 0;
  tmpIni = s;
  ultimoPrimo[hijos[e]] = -2;
  for (int i = (s); i <= (e); i++) {
    hijo = hijos[i];
    if (ultimoPrimo[hijo] != actual) {
      if (cuenta > maxx) {
        maxx = cuenta;
        fin = pos;
        ini = tmpIni;
      }
      actual = ultimoPrimo[hijo];
      cuenta = cantidad[hijo];
      tmpIni = pos;
    } else {
      cuenta += cantidad[hijo];
    }
    if (hijo != 1) {
      factorizacion[hijo][ultimoPrimo[hijo]]--;
      if (!factorizacion[hijo][ultimoPrimo[hijo]]) ultimoPrimo[hijo]--;
    }
    pos++;
  }
  return maxx;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  for (int i = (1); i <= (n); i++) {
    cin >> k;
    if (k == 0) k = 1;
    cantidad[k]++;
    if (k > maxN) maxN = k;
  }
  for (int i = (2); i <= (sqrt(5001)); i++) {
    if (criba[i]) continue;
    for (int j = 2 * i; j <= maxN; j += i) criba[j] = 1;
  }
  for (int i = (2); i <= (5001 - 1); i++)
    if (!criba[i]) primos.push_back(i);
  for (int i = (2); i <= (maxN); i++) {
    for (int j = 0; factorizacion[i - 1][j] > 0; j++)
      factorizacion[i][j] = factorizacion[i - 1][j];
    int j;
    for (int f = i, j = 0; f > 1;) {
      if (f % primos[j] == 0) {
        factorizacion[i][j]++;
        f /= primos[j];
      } else {
        j++;
      }
    }
    for (int j = 0; factorizacion[i][j] > 0; j++) {
      numFactores[i] += factorizacion[i][j];
      ultimoPrimo[i] = j;
    }
  }
  for (int i = (2); i <= (maxN); i++) costo += numFactores[i] * cantidad[i];
  for (int i = (1); i <= (maxN); i++)
    if (cantidad[i]) hijos.push_back(i);
  hijos.push_back(1);
  s = 0;
  e = hijos.size() - 1;
  ultimoPrimo[1] = -2;
  while (true) {
    hijoMayor = centroide();
    if (hijoMayor > (n >> 1) && hijos[ini] != 1) {
      costo += n - (hijoMayor << 1);
      s = ini;
      e = fin;
      if (ultimoPrimo[hijos[s]] == -1) break;
    } else
      break;
  }
  cout << costo;
  return 0;
}
