#include <bits/stdc++.h>
using namespace std;
const int K = 5005;
const int N = 1000009;
bool isp[K];
long long fac[K];
long long maxfac[K];
long long maxfaccnt[K];
vector<long long> prime;
long long deep1[K];
long long deep2[K];
long long n;
long long A[N];
long long cnt[K];
long long son[K];
bool del[K];
long long prep[K];
int main() {
  for (int i = 2; i <= 5000; i++) {
    isp[i] = 1;
    fac[i] = i;
  }
  for (int i = 2; i <= 5000; i++) {
    if (isp[i]) {
      for (int j = i + i; j <= 5000; j += i) {
        isp[j] = 0;
      }
      prime.push_back(i);
    }
  }
  for (int i = 2; i <= 5000; i++) {
    if (fac[i] == i) {
      for (int j = i + i; j <= 5000; j += i) {
        if (fac[j] == j) {
          fac[j] = i;
        }
      }
    }
  }
  for (int i = 2; i <= 5000; i++) {
    if (isp[i]) {
      deep1[i] = 1;
    } else {
      deep1[i] = deep1[i / fac[i]] + 1;
    }
  }
  for (int i = 2; i <= 5000; i++) {
    deep2[i] = deep2[i - 1] + deep1[i];
  }
  scanf("%lld", &n);
  long long ans1 = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &A[i]);
    ans1 += deep2[A[i]];
    cnt[A[i]]++;
  }
  for (int i = 2; i <= 5000; i++) {
    if (isp[i]) {
      maxfac[i] = i;
      maxfaccnt[i] = 1;
    } else {
      maxfac[i] = maxfac[i - 1];
      long long t = maxfac[i];
      while (t <= i) {
        maxfaccnt[i] += i / t;
        t *= maxfac[i];
      }
    }
    son[maxfac[i]] += cnt[i];
  }
  long long u = 0;
  for (int i = 2; i <= 5000; i++) {
    if (son[i] > n - son[i]) {
      u = i;
      ans1 = ans1 - son[i] + (n - son[i]);
      break;
    }
  }
  if (u == 0) {
    printf("%lld\n", ans1);
    return 0;
  }
  int len = prime.size();
  prep[2] = 1;
  for (int i = 1; i < len; i++) {
    prep[prime[i]] = prime[i - 1];
  }
  while (u != 0) {
    memset(son, 0, sizeof(son));
    int v = 0;
    for (int i = 2; i <= 5000; i++) {
      if (del[i]) {
        continue;
      }
      if (maxfac[i] != u) {
        del[i] = 1;
      } else {
        maxfaccnt[i]--;
        if (maxfaccnt[i] == 0) {
          maxfac[i] = prep[maxfac[i]];
          long long t = maxfac[i];
          while (t <= i && t > 1) {
            maxfaccnt[i] += i / t;
            t *= maxfac[i];
          }
        }
        if (maxfac[i] <= u) {
          son[maxfac[i]] += cnt[i];
        }
      }
    }
    for (int i = 2; i <= 5000 && i <= u; i++) {
      if (son[i] > n - son[i]) {
        v = i;
        ans1 = ans1 - son[i] + (n - son[i]);
        break;
      }
    }
    u = v;
  }
  printf("%lld\n", ans1);
  return 0;
}
