#include #define rep(i, n) for (int i = 0; i < (int)(n); ++i) #define all(v) begin(v), end(v) using namespace std; using ll = long long; template bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; } constexpr ll inf = 1e18; class UnionFind { vector par; public: UnionFind(int n) : par(n, -1) {} int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); } bool merge(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; return true; } int size(int x) { return -par[find(x)]; } }; int main() { int N; cin >> N; vector A(N); rep (i, N) cin >> A[i]; int M = *max_element(all(A)) + 1; vector> divs(M); for (int i = 1; i < M; ++i) { for (int j = i; j < M; j += i) divs[j].push_back(i); } ll ans = 0; UnionFind uf(N); while (uf.size(0) != N) { vector> grp(N); rep (i, N) grp[uf.find(i)].push_back(i); vector mn1(N, inf); vector mn2(N, -1); rep (_, 2) { vector memo1(M, inf); vector memo2(M, -1); rep (g, N) { for (int i : grp[g]) { for (int d : divs[A[i]]) { if (memo1[d] != inf && chmin(mn1[g], memo1[d] * A[i])) { mn2[g] = memo2[d]; } } } for (int i : grp[g]) { for (int d : divs[A[i]]) { if (chmin(memo1[d], A[i] / d)) { memo2[d] = g; } } } } reverse(all(grp)); reverse(all(mn1)); reverse(all(mn2)); rep (i, N) mn2[i] = N - 1 - mn2[i]; } rep (i, N) { if (mn2[i] == -1) continue; if (uf.merge(i, mn2[i])) ans += mn1[i]; } } cout << ans << endl; }