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

class Factorization {
public:
    vector<int> L;

    Factorization(int N) {
        L.resize(N + 1);
        for (int i = 0; i <= N; ++i) {
            L[i] = i;
        }
        for (int i = 2; i <= N; ++i) {
            if (i != L[i]) continue;
            for (int j = 2 * i; j <= N; j += i) {
                L[j] = i;
            }
        }
    }

    vector<pair<int, int>> get(int n) {
        vector<pair<int, int>> D;
        if (n <= 1) return D;
        while (n != 1) {
            int cnt = 0;
            int now = L[n];
            while (n % now == 0) {
                cnt++;
                n /= now;
            }
            D.push_back({now, cnt});
        }
        return D;
    }
};

class UnionFind {
public:
    vector<int> par, rank, size;

    UnionFind(int n) {
        par.resize(n);
        rank.resize(n, 0);
        size.resize(n, 1);
        for (int i = 0; i < n; ++i) {
            par[i] = i;
        }
    }

    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }

    void union_sets(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (rank[x] < rank[y]) {
                swap(x, y);
            }
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
            par[y] = x;
            size[x] += size[y];
        }
    }

    bool is_same(int x, int y) {
        return find(x) == find(y);
    }

    int get_size(int x) {
        return size[find(x)];
    }
};

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    const int M = 2 * 100000 + 5;
    Factorization F(M);
    int now = N;

    unordered_map<int, int> D;
    for (int a : A) {
        for (auto [k, v] : F.get(a)) {
            if (D.find(k) == D.end()) {
                D[k] = now;
                now++;
            }
        }
    }

    UnionFind U(now);
    int mi = LLONG_MAX;
    for (int i = 0; i < N; ++i) {
        for (auto [k, v] : F.get(A[i])) {
            mi = min(mi, k);
            U.union_sets(i, D[k]);
        }
    }

    set<int> S;
    for (int i = 0; i < N; ++i) {
        S.insert(U.find(i));
    }

    if (mi == 2) {
        cout << (S.size() - 1) * 2 << endl;
    } else {
        cout << min(2 * S.size(), mi * (S.size() - 1)) << endl;
    }

    return 0;
}