#include #include #include #include #include #include #include int main() { using namespace std; unsigned N; cin >> N; vector A(N); for (auto&& a : A) cin >> a; ranges::sort(A); const auto M{ranges::max(A)}; vector> values(M + 1); unsigned long ans{}; for (const auto &[i, a] : A | views::enumerate) if (empty(values[a])) values[a].emplace_back(i); else ans += a; { vector tmp; vector sieve(M + 1, 1); for (unsigned p{2}; p <= M; ++p) if (sieve[p]) { for (const auto j : views::iota(1) | views::take_while([p, M](const auto j){return j * p <= M;}) | views::reverse) { sieve[j * p] = 0; tmp.resize(size(values[j * p]) + size(values[j])); swap(tmp, values[j]); ranges::merge(values[j * p], tmp, begin(values[j])); } } } set> edges; for (const auto &vs : values) if (!empty(vs)) for (const auto first{vs[0]}; const auto rest : vs | views::drop(1)) edges.emplace(make_tuple(lcm(A[first] + 0ul, A[rest]), first, rest)); vector uf(N), sz(N, 1); iota(begin(uf), end(uf), 0u); const auto find{[&uf](auto i) { while (i != uf[i]) i = uf[i] = uf[uf[i]]; return i; }}; const auto unite{[&uf, &sz, &find](auto i, auto j) { i = find(i); j = find(j); if (i == j) return false; if (sz[i] < sz[j]) swap(i, j); sz[i] += sz[j]; uf[j] = i; return true; }}; for (const auto& [c, i, j] : edges) if (unite(i, j)) ans += c; cout << ans << endl; return 0; }