#include <bits/stdc++.h>
inline int getint() {
  int x = 0, p = 1;
  char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int M = 1000000;
const int B = 5005;
int n, pos[B], cnt, c[M], fc[M];
long long res[M], f[M];
map<int, int> to[M], dis[M];
bool vis[B];
vector<int> prime;
vector<pair<int, int> > g[M];
int go(int x, vector<pair<int, int> > &v) {
  if (v.size() && !v.back().second) v.pop_back();
  if (v.empty()) return x;
  if (to[x].find(v.back().first) == to[x].end()) {
    ++cnt;
    to[x][v.back().first] = cnt;
    dis[x][v.back().first] = v.back().second;
    v.pop_back();
    return go(cnt, v);
  }
  int ans = dis[x][v.back().first];
  if (ans <= v.back().second) {
    v.back().second -= ans;
    return go(to[x][v.back().first], v);
  }
  int t = to[x][v.back().first];
  ++cnt;
  to[x][v.back().first] = cnt;
  to[cnt][v.back().first] = t;
  dis[x][v.back().first] = v.back().second;
  dis[cnt][v.back().first] = ans - v.back().second;
  v.pop_back();
  return go(cnt, v);
}
void init(int x, int p) {
  for (int(i) = 0; (i) < (g[x].size()); (i)++) {
    int to = g[x][i].first, len = g[x][i].second;
    if (to == p) continue;
    init(to, x);
    c[x] += c[to];
    res[x] += res[to] + 1ll * len * c[to];
  }
}
void dfs(int x, int p) {
  long long h = f[x];
  int hc = fc[x];
  res[x] += f[x];
  for (int(i) = 0; (i) < (g[x].size()); (i)++) {
    int to = g[x][i].first, len = g[x][i].second;
    if (to == p) continue;
    h += res[to] + 1ll * c[to] * len;
    hc += c[to];
  }
  for (int(i) = 0; (i) < (g[x].size()); (i)++) {
    int to = g[x][i].first, len = g[x][i].second;
    if (to == p) continue;
    f[to] += h - res[to] + 1ll * (hc - 2ll * c[to]) * len;
    fc[to] += hc - c[to];
  }
  for (int(i) = 0; (i) < (g[x].size()); (i)++) {
    int to = g[x][i].first;
    if (to == p) continue;
    dfs(to, x);
  }
}
int main() {
  n = getint();
  for (int i = 2; i <= 5000; i++) {
    if (!vis[i]) prime.emplace_back(i);
    for (int(j) = 0; (j) < (prime.size()); (j)++)
      if (prime[j] * i <= 5000) {
        int to = prime[j] * i;
        vis[to] = true;
        if (i % prime[j] == 0) break;
      }
  }
  pos[0] = pos[1] = 0;
  for (int i = 2; i <= 5000; i++) {
    vector<pair<int, int> > v;
    for (int(j) = 0; (j) < (prime.size()); (j)++) {
      if (i < prime[j]) break;
      int x = prime[j], ans = 0;
      while (x <= i) {
        ans += i / x;
        x *= prime[j];
      }
      v.emplace_back(j, ans);
    }
    pos[i] = go(0, v);
  }
  for (int(i) = 0; (i) < (cnt + 1); (i)++) {
    map<int, int>::iterator itx = to[i].begin(), ity = dis[i].begin();
    while (itx != to[i].end()) {
      g[i].emplace_back(itx->second, ity->second);
      ++itx;
      ++ity;
    }
  }
  for (int(i) = 0; (i) < (n); (i)++) {
    int x = getint();
    c[pos[x]]++;
    fc[pos[x]]++;
  }
  init(0, -1);
  dfs(0, -1);
  long long ans = 2e18;
  for (int(i) = 0; (i) < (cnt + 1); (i)++) ans = min(ans, res[i]);
  cout << ans << endl;
  return 0;
}
