#define  _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include<stdio.h>
#include<random>
#include<algorithm>
#include<array>
#include<chrono>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> PII;
#define fi first
#define sc second
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rep_(i, l, r) for (ll i = (l); i >= (r); --i)
//#include<atcoder/fenwicktree>//斜杠后面填数据类型
//using namespace atcoder;
using namespace std;
std::mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());//ull x=rng()//随机数
const ll P = 1e9 + 7;
const ll Inf = 1e5;
const ll M = 5e5 + 7;
const ll N = 2e6 + 7;
const double eps = 1e-6;
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}
long long qmin(long long a, long long b) {
    long long res = 1;
    a %= P;
    while (b) {
        if (b & 1)res = res * a % P;
        b >>= 1;
        a = a * a % P;
    }
    return res;
}
long long inv(long long x) {
    return qmin(x, P - 2);
}
inline ll read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
int lowbit(int x) {
    return x & (-x);
}
// 
// 
//Tarjan求强连通分量
//const int N = 1e4 + 5;
//vector<int> p[N];
//int dfn[N], low[N], num;
//bool ins[N];
//int scc_cnt;
//int scc_id[N], color[N];
//int stk[N], top;
//void tarjan(int x) {
//	dfn[x] = low[x] = ++num;
//	stk[++top] = x;
//	ins[x] = true;
//	for (auto &y : p[x]) {
//		if (!dfn[y]) {
//			tarjan(y);
//			low[x] = min(low[x], low[y]);
//		}
//		else if (ins[y]) low[x] = min(low[x], dfn[y]);
//	}
//	if (low[x] == dfn[x]) {
//		int y;
//		++scc_cnt;
//		do {
//			y = stk[top--];
//			ins[y] = false;
//			scc_id[y] = scc_cnt;
//			color[y] = scc_cnt;
//		} while (x != y);
//	}
//}
//struct point {
//    ll x, y;
//}p[N];
//ll mj(point a, point b, point c) {
//    //cout << "..." << abs((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)) << endl;
//    return abs((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x));
//}
//链式前向星
//int acnt;
//int head[N], nxt[M], flow[M], to[M], from[M];
//void addadge(int u, int v, int f) {
//    flow[acnt] = f;
//    //cost[acnt] = c;
//    nxt[acnt] = head[u];
//    to[acnt] = v;
//    head[u] = acnt;
//    from[acnt] = u;
//    ++acnt;
//}
//struct Pt {
//    ll x, y;
//    Pt operator-(Pt b)const { return Pt{ x - b.x,y - b.y }; };
//    ll crs(Pt b)const { return x * b.y - y * b.x; };
//    bool operator<(Pt b)const { return std::abs(x - b.x) < eps ? y < b.y : x < b.x; };
//    static ll cross(Pt p, Pt a, Pt b) { return (a - p).crs(b - p); };//叉积
//    ll pf() { return { x * x + y * y }; };
//    static ll len(Pt a, Pt b) { return sqrt((a - b).pf()); };
//};
//vector<Pt>Andrew(vector<Pt>& vec) {
//    int n = vec.size();
//    sort(vec.begin(), vec.begin() + n);
//    if (n < 2)return vector<Pt>();
//    vector<Pt>tb;
//    vector<Pt>st(n * 2 + 7);
//    int top = 1;
//    st[0] = vec[0];
//    st[1] = vec[1];
//    rep(i, 2, n - 1) {
//        while (top && Pt::cross(st[top - 1], st[top], vec[i]) <= 0) {
//            top--;
//        }
//        st[++top] = vec[i];
//    }
//    st[++top] = vec[n - 2];
//    int o = top;
//    rep_(i, n - 3, 0) {
//        while (top >= o && Pt::cross(st[top - 1], st[top], vec[i]) <= 0) {
//            top--;
//        }
//        st[++top] = vec[i];
//    }
//    for (int i = 0; i <= top; ++i) {
//        tb.push_back(st[i]);
//    }
//    return tb;
//}
//int getmax(vector<Pt>& vec) {
//    ll re = 0;
//    int top = vec.size() - 1;
//    if (top <= 2)return (vec[0]-vec[1]).pf();
//    int j = 2;
//    rep(i, 0, top - 1) {
//        while (Pt::cross(vec[i], vec[i + 1], vec[j]) < Pt::cross(vec[i], vec[i + 1], vec[j + 1])) { j = (j + 1 == top ? 0 : j + 1); }
//        re = max({ re,(vec[i] - vec[j]).pf(),(vec[i + 1] - vec[j]).pf() });
//    }
//    return re;
//}
//struct node {  //01trie
//    int cnt, son[2];
//}trie[20*N];
//int num = 1;
//inline void insert(int x) {
//    int now = 1;
//    trie[1].cnt++;
//    rep_(i, 30, 0) {
//        int next = (x >> i) & 1;
//        if (!trie[now].son[next])trie[now].son[next] = ++num;
//        now = trie[now].son[next];
//        trie[now].cnt++;
//    }
//}
//inline int query(int x) {
//    int now = 1;
//    int ans = 0;
//    rep(i, 30, 0) {
//        int next = (x >> i) & 1;
//        if (!trie[trie[now].son[next]].cnt)next = !next;
//        ans = (ans << 1) + next;
//        now = trie[now].son[next];
//        trie[now].cnt--;
//    }
//    return ans ^ x;
//}
//namespace pam {
//    const int knode = N << 1;
//    int nown, nodenum, last, tr[knode][26], len[knode], fail[knode];
//    int dep[knode];
//    char t[N];
//    int newnode(int len_) {
//        ++nodenum;
//        memset(tr[nodenum], 0, sizeof(tr[nodenum]));
//        len[nodenum] = len_;
//        fail[nodenum] = dep[nodenum] = 0;
//        return nodenum;
//    }
//    void init() {
//        nodenum = -1;
//        last = 0;
//        t[nown = 0] = '$';
//        newnode(0), newnode(-1);
//        fail[0] = 1;
//    }
//    int getfail(int x_) {
//        while (t[nown - len[x_] - 1] != t[nown])x_ = fail[x_];
//        return x_;
//    }
//    void insert(char ch_) {
//        t[++nown] = ch_;
//        int now = getfail(last);
//        if (!tr[now][ch_ - 'a']) {
//            int x = newnode(len[now] + 2);
//            fail[x] = tr[getfail(fail[now])][ch_ - 'a'];
//            tr[now][ch_ - 'a'] = x;
//        }
//        last = tr[now][ch_ - 'a'];
//        dep[last] = dep[fail[last]] + 1;
//    }
//};
//void manacher(string s) {
//    string t = "$#";
//    for (auto c : s) {
//        t += c;
//        t += '#';
//    }
//    int n = t.size();
//    vector<int>vec(n, 0);
//    int mx = 0;//边界
//    int id = 0;//中心
//    for (int i = 1; i < n; ++i) {
//        vec[i] = mx > i ? min(vec[2 * id - i], mx - i) : 1;
//        while (t[i + vec[i]] == t[i - vec[i]])++vec[i];
//        if (mx < i + vec[i]) {
//            mx = i + vec[i];
//            id = i;
//        }
//    }
//}
//struct SAM {
//    const static int maxn = 2e5 + 7;
//    int len[maxn << 1], link[maxn << 1];
//    int ch[maxn << 1][26];
//    int siz, last;
//    vector<int>v[maxn << 1];
//    void init() {
//        memset(len, 0, sizeof(len));
//        memset(link, 0, sizeof(link));
//        memset(ch, 0, sizeof(ch));
//        rep(i, 0, (maxn << 1) - 5)v[i].clear();
//        siz = last = 0;
//        link[0] = -1;
//    }
//    void extend(string s) {
//        int n = s.size();
//        rep(i, 0, n - 1) {
//            int cur = ++siz, p = last, c = s[i] - 'a';
//            len[cur] = len[p] + 1;
//            while (p != 1 && !ch[p][c]) {
//                ch[p][c] = cur;
//                p = link[p];
//            }
//            if (p == -1)link[cur] = 0;
//            else {
//                int q = ch[p][c];
//                if (len[q] == len[p] + 1) link[cur] = q;
//                else {
//                    int copy = ++siz;
//                    len[copy] = len[p] + 1;
//                    link[copy] = link[q];
//                    rep(j, 0, 25) ch[copy][j] = ch[q][j];
//                    while (p != -1 && ch[p][c] == q) {
//                        ch[p][c] = copy;
//                        p = link[p];
//                    }
//                    link[q] = link[cur] = copy;
//                }
//            }
//            last = cur;
//        }
//        rep(i, 1, siz)v[link[i]].push_back(i);
//    }
//};
namespace flow {
    int tot, s, t, ans, head[N], cur[N], d[N];
    bool vis[N];
    std::queue<int> q;
    struct graph {
        int v, w, c, next;
    }edge[N];
    inline void add(int u, int v, int w, int c) {
        edge[++tot] = { v,w,c,head[u] }, head[u] = tot;
        edge[++tot] = { u,0,-c,head[v] }, head[v] = tot;
    }
    inline bool spfa() {
        rep(i, 1, t) d[i] = -1e9;
        q.push(s), d[s] = 0, vis[s] = true;
        while (!q.empty()) {
            int u = q.front();
            q.pop(), vis[u] = false;
            for (int i = head[u]; i; i = edge[i].next) {
                int v = edge[i].v, w = edge[i].w, c = edge[i].c;
                if (w && d[u] + c > d[v]) {
                    d[v] = d[u] + c;
                    if (!vis[v]) vis[v] = true, q.push(v);
                }
            }
        }
        return d[t] != -1e9;
    }
    inline int dfs(int u, int now) {
        if (u == t) return now;
        int rst = now;
        vis[u] = true;
        for (int& i = cur[u]; i; i = edge[i].next) {
            int v = edge[i].v, w = edge[i].w, c = edge[i].c;
            if (!w || d[u] + c != d[v] || vis[v]) continue;
            int k = dfs(v, std::min(w, rst));
            if (!k) d[v] = -1e9;
            else edge[i].w -= k, edge[i ^ 1].w += k, rst -= k, ans += k * c;
            if (!rst) break;
        }
        vis[u] = false;
        return now - rst;
    }
    inline int dinic() {
        int maxf = 0;
        while (spfa()) {
            rep(i, 1, t) cur[i] = head[i];
            maxf += dfs(s, 1e9);
        }
        return maxf;
    }
}
using namespace flow;
int a[N];
int cnt;
vector<ll>prime;
map<ll, ll>mp;
void init(ll x) {
    for (ll i = 1; i * i <= x; ++i) {
        if (x % i == 0) {
            if (!mp.count(i))mp[i] = ++cnt;
            if (!mp.count(x / i))mp[x / i] = ++cnt;
        }
    }
    for (ll i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            prime.push_back(i);
            while (x % i == 0)x /= i;
        }
    }
    if (x != 1)prime.push_back(x);
}
void solve() {
    int n;
    cin >> n;
    cnt = 0;
    rep(i, 1, n) {
        cin >> a[i];
        init(a[i]);
    }
    s = ++cnt;
    t = ++cnt;
    tot = 1;
    std::sort(prime.begin(), prime.end());
    prime.erase(std::unique(prime.begin(), prime.end()), prime.end());
    rep(i,1,n) add(s, mp[a[i]], 1, 0);
    for (auto [x, y] : mp) {
        //cout << x <<' '<<a[1] % x<< endl;
        add(y, t, 1, 0);
        for (auto zs : prime) {
            if (zs > x)break;
            if (x % zs == 0) {
                add(y, mp[x / zs], n, 1);
            }
        }
    }
    dinic();
    cout << ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cout << fixed << setprecision(2);
    //cin >> t;
    while (t--) solve();
    return 0;
}