#include <bits/stdc++.h>
using namespace std;
const int N = 10000;
const int Max = 1e6 + 1;
int n, m;
long long ans;
int a[Max];
int d[N], pack[N];
int biggest_prime[N];
int counts_prime[N][700], counts_prime_total[N][700];
vector<int> prime;
void Find_Prime() {
  vector<int> h;
  for (int i = 0; i <= 5100; i++) h.push_back(0);
  for (int i = 2; i <= 5100; i++) {
    if (!h[i]) {
      h[i] = i;
      prime.push_back(i);
    }
    int j = 0;
    while (j < prime.size() && prime[j] <= h[i] && prime[j] * i <= 5100) {
      h[prime[j] * i] = prime[j];
      j++;
    }
  }
}
void Init() {
  Find_Prime();
  for (int i = 2; i <= 5000; i++) {
    int x = i;
    for (int j = 0; j <= prime.size() - 1; j++) {
      counts_prime[i][j] = counts_prime[i - 1][j];
      while (x % prime[j] == 0) {
        counts_prime[i][j]++, x /= prime[j];
      }
      counts_prime_total[i][j] =
          counts_prime_total[i][j - 1] + counts_prime[i][j];
      if (counts_prime[i][j] > 0) biggest_prime[i] = j;
    }
  }
}
void Solve_Pack(int num) {
  for (int i = num; i >= 0; i--) {
    int c = 1;
    while (true) {
      int counts = 0;
      for (int j = prime[num]; j <= prime[num + 1] - 1; j++)
        if (counts_prime[j][i] >= c) {
          counts += d[j];
        }
      if (counts > n / 2) {
        ans += n - 2 * counts;
      } else {
        for (int j = prime[num]; j <= prime[num + 1] - 1; j++)
          if (counts_prime[j][i] != c - 1) d[j] = 0;
        break;
      }
      c++;
    }
  }
}
void Solve() {
  m = 5000;
  int l = 1, r = 0;
  while (a[l] == 1 && l <= n) l++, r++;
  if (l > n) return;
  for (int i = 0; i <= prime.size() - 1; i++) {
    while (r + 1 <= n && biggest_prime[a[r + 1]] == i) r++;
    pack[i] = r - l + 1;
    l = r + 1;
    if (l > n) break;
  }
  for (int i = 0; i <= prime.size() - 1; i++)
    if (pack[i] > n / 2) Solve_Pack(i);
}
int main() {
  Init();
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] = a[i] == 0 ? 1 : a[i];
    d[a[i]]++;
    ans += counts_prime_total[a[i]][biggest_prime[a[i]]];
  }
  sort(a + 1, a + 1 + n);
  Solve();
  cout << ans;
}
