#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5e5 + 10;
struct MCFGraph {
    struct Edge {
        int v, c, f;
        Edge(int v, int c, int f) :v(v), c(c), f(f) {}
    };
    int n;
    vector<Edge>e;
    vector<vector<int>>g;
    vector<LL>h, dis;
    vector<int>pre;

    MCFGraph(int n) :n(n), g(n + 1) {}

    void add(int u, int v, int c, int f) {
        // cerr << u << " " << v << " " << c << " " << f << "\n";
        g[u].push_back(e.size());
        e.emplace_back(v, c, f);
        g[v].push_back(e.size());
        e.emplace_back(u, 0, -f);
    }

    bool dijkstra(int s, int t) {
        dis.assign(n + 1, numeric_limits<LL>::max());//LL的最大值
        pre.assign(n + 1, -1);
        priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>>q;
        dis[s] = 0;
        q.emplace(0, s);
        while (!q.empty()) {
            auto [d, u] = q.top();q.pop();
            if (dis[u] < d)continue;
            for (int i : g[u]) {
                auto [v, c, f] = e[i];
                if (c > 0 and dis[v] > d + h[u] - h[v] + f) {
                    dis[v] = d + h[u] - h[v] + f;
                    pre[v] = i;
                    q.emplace(dis[v], v);
                }
            }
        }
        return dis[t] != numeric_limits<LL>::max();
    }

    pair<int, LL>flow(int s, int t) {
        int flow = 0;
        LL cost = 0;
        h.assign(n + 1, 0);
        while (dijkstra(s, t)) {
            for (int i = 1;i <= n;i++)
                h[i] += dis[i];
            int mn = numeric_limits<int>::max();//int最大值
            for (int i = t;i != s;i = e[pre[i] ^ 1].v)
                mn = min(mn, e[pre[i]].c);
            for (int i = t;i != s;i = e[pre[i] ^ 1].v) {
                e[pre[i]].c -= mn;
                e[pre[i] ^ 1].c += mn;
            }
            flow += mn;
            cost += 1LL * mn * h[t];
        }
        return make_pair(flow, cost);
    }
};

int p[N];
void solve() {
    int n;cin >> n;
    vector<int>a(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    int s = 0, t = 5e5 + 10;
    MCFGraph f(t);
    unordered_map<int, int>mp;
    int cnt = 0;

    auto id = [&](int x) {
        if (!mp.count(x))return mp[x] = ++cnt;
        return mp[x];
    };

    for (int i = 1;i <= n;i++) {
        f.add(s, id(a[i]), 1, 0);
        int x = a[i];
        for (int j = 1;j <= x / j;j++) {
            if (x % j == 0) {
                id(j);
                if (x / j != j)id(x / j);
            }
        }
    }
    // for (auto [x, id] : mp) {
    //     cout << x << " " << id << "\n";
    // }


    for (auto [x, id] : mp) {
        int now = x;
        for (int i = 2;i <= now / i;i++) {
            while (now % i == 0) {
                p[id]++;
                now /= i;
            }
        }
        if (now > 1)p[id]++;
        f.add(id, t, 1, 0);
    }

    vector<int>fac;
    for (int i = 1;i <= n;i++) {
        int x = a[i];
        fac.clear();
        // cerr << "now::" << x << "\n";
        for (int j = 1;j <= x / j;j++) {
            if (x % j == 0) {
                // cerr << format("{}->{}\n", x, j);
                fac.push_back(j);
                if (x / j != j) {
                    fac.push_back(x / j);
                    // cerr << format("{}->{}\n", x, x / j);
                }
            }
        }
        sort(fac.begin(), fac.end());
        int cc = 0;
        for (auto x : fac) {
            cc++;
            f.add(id(a[i]), id(x), 1, -(p[id(a[i])] - p[id(x)]));
            if (cc > n)break;
        }
    }
    auto [flow, cost] = f.flow(s, t);
    cout << -cost << "\n";

}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // #ifdef LOCAL
        // freopen("data.in", "r", stdin);
        // freopen("data.out", "w", stdout);
    // #endif
        // cin >> T;
    while (T--)
        solve();
    return 0;
}