#include using namespace std; const long long MODULO = 1e9 + 7; int N; int A[1000001]; vector indexes[100001]; vector factors[100001]; long long result = 0; bitset<1000001> visited; int M; vector v; vector>> edges; namespace DSU { vector dsu, min; void init(const int& size) { dsu.clear(), dsu.resize(size + 1, -1); min.clear(), min.resize(size + 1); iota(min.begin(), min.end(), 0); } int find(const int& u) { return dsu[u] < 0 ? u : dsu[u] = find(dsu[u]); } bool unite(int u, int v) { u = find(u), v = find(v); if (u == v) return false; if (dsu[u] < dsu[v]) swap(u, v); dsu[v] += dsu[u]; dsu[u] = v; if (A[min[u]] < A[min[v]]) min[v] = min[u]; return true; } int getComponentMin(const int& u) { return min[find(u)]; } } void KruskalsAlgorithm() { sort(edges.begin(), edges.end()); int mstEdgesCount = 0; DSU::init(M); for (auto &[weight, edge] : edges) { int i = edge.first, j = edge.second; if (DSU::unite(i, j)) { result += weight; if (++mstEdgesCount == M - 1) return; } } } int main() { // freopen("inp.txt", "r", stdin); // freopen("out.txt", "w", stdout); ios::sync_with_stdio(false); for (int i = 1; i <= 100000; i++) for (int j = i; j <= 100000; j += i) factors[j].push_back(i); cin >> N; for (int i = 1; i <= N; i++) cin >> A[i]; sort(A + 1, A + N + 1); for (int i = 1; i <= N; i++) indexes[A[i]].push_back(i); DSU::init(N); for (int i = 1; i <= N; i++) for (auto &f : factors[A[i]]) if (!indexes[f].empty() && indexes[f].front() < i) { DSU::unite(indexes[f].front(), i); result += A[i]; break; } for (int i = 1; i <= N; i++) { int u = DSU::find(i); if (visited[u]) continue; visited[u] = true; v.push_back(A[DSU::getComponentMin(u)]); } M = (int)v.size(); for (int i = 0; i < M; i++) for (int j = 0; j < i; j++) edges.emplace_back(lcm(1ll * v[i], 1ll * v[j]), make_pair(i, j)); KruskalsAlgorithm(); cout << result; }