#include<bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int, int> pii;
typedef long long LL;
typedef unsigned long long uLL;

const int inf32 = 1e9;
const LL inf64 = 1e18;

struct dinic {
    const LL inf = 1e18;

    struct edge {
        LL v, nxt, cap, flow, cost;
    };

    vector<edge> e;
    int n, S, T;
    LL maxflow, mncost;
    vector<int> head, cur, vis;
    vector<LL> dis;

    dinic(int x) {init(x);}

    void init(int x) {
        n = x;
        S = 0, T = n + 1, maxflow = 0;
        e.clear();
        head.assign(n + 5, -1);
        cur.assign(n + 5, -1);
        vis.assign(n + 5, 0);
        dis.assign(n + 5, inf);
    }
    void add_edge(int u, int v, LL w, LL cost) {
        // cerr << u << ' ' << v << ' ' << w << ' ' << cost << endl;
        e.push_back({v, head[u], w, 0, cost});
        head[u] = e.size() - 1;
        e.push_back({u, head[v], 0, 0, -cost});
        head[v] = e.size() - 1;
    }
    int spfa() {
        dis.assign(n + 5, inf);
        vis.assign(n + 5, 0);
        queue<int> q;
        q.push(S);
        dis[S] = 0, vis[S] = 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            vis[u] = 0;

            for (int i = head[u]; ~i; i = e[i].nxt) {
                int v = e[i].v;
                if (e[i].cap > e[i].flow && dis[v] > dis[u] + e[i].cost) {
                    dis[v] = dis[u] + e[i].cost;
                    if (!vis[v]) q.push(v), vis[v] = 1;
                }
            }
        }
        return dis[T] != inf;
    }
    LL dfs(int u, LL flow) {
        if (u == T || !flow) return flow;
        vis[u] = 1;
        LL ret = 0;

        for (int i = cur[u]; ~i; i = e[i].nxt) {
            cur[u] = i;
            int v = e[i].v;
            LL d = 0;
            
            if (!vis[v] && dis[v] == dis[u] + e[i].cost && (d = dfs(v, min(flow - ret, e[i].cap - e[i].flow)))) {
                ret += d;
                e[i].flow += d;
                e[i ^ 1].flow -= d;
                if (ret == flow) return ret;
            }
        }
        vis[u] = 0;
        return ret;
    }
    void gets_maxflow() {
        maxflow = mncost = 0;
        int x;
        while (spfa()) {
            cur = head;
            vis.assign(n + 5, 0);
            while(x = dfs(S, inf)) {
                maxflow += x;
                mncost += x * dis[T];
            }
        }
    }
};

const int maxn = 1e7 + 5;

int isprime[maxn], prime[maxn];
int prime_cnt = 0;

void init(int n) {
    for (int i = 2; i <= n; i++) {
        if (!isprime[i]) {prime[++prime_cnt] = i;}
        for (int j = 1; j <= prime_cnt; j++) {
            if (prime[j] * i > n) break;
            isprime[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

signed main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(0);

    init(1e5);
    // freopen("text.in","r",stdin);
    int T = 1;
    // cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n + 5, 0);
        for (int i = 1; i <= n; i++) cin >> a[i];

        // const int maxm = 1e6 + 5;

        map<int, int> mp, id;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= a[i]; j++) {
                if (a[i] % j == 0) {
                    mp[j] = mp[a[i] / j] = 1;
                }
            }
        }

        int cnt = 0;
        for (auto [x, y] : mp) {
            if (!id.count(x)) id[x] = ++cnt;
        }

        vector<int> nxt(cnt + 5, 0), ff(cnt + 5, 0);
        dinic G(cnt);

        for (auto [x, y] : mp) {
            if (id[x] != 1) G.add_edge(id[x], 1, inf64, -1);
            for (int j = 1; prime[j] * prime[j] <= x && j <= prime_cnt; j++) {
                if (x % prime[j] == 0) G.add_edge(id[x], id[x / prime[j]], inf64, -1), G.add_edge(id[x], id[prime[j]], inf64, -1);
            }
            G.add_edge(id[x], G.T, 1, 0);
        }
        for (int i = 1; i <= n; i++) G.add_edge(G.S, id[a[i]], 1, 0);

        G.gets_maxflow();

        // cerr<<G.maxflow << ' ' << G.mncost<<endl;
        cout << -G.mncost << "\n";
        // cerr << cnt << endl;

    }

    return 0;
}