#include <bits/stdc++.h>
#define ll long long
#define db double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define vi vector<int>
#define vll vector<long long>
#define fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)
#define allr(x) rbegin(x), rend(x)
#define szx(x) ((int)(x).size())
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; ++i)
#define ROF(i, a, b) for (int i = a, _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define endl '\n'
#define inf 1000000007
#define infll 1000000000000000007
#define mod 1000000007
using namespace std;
void setIO() {
ios::sync_with_stdio(0);
cin.tie(0);
}
void openFile(string filename = "") {
if (!filename.empty())
if (ifstream(filename + ".in")) {
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
}
int n;
int p[100005];
vector<int> x[10000010];
int fc[10000010];
void sieve() {
FOR(i, 1, 1e7)
if (szx(x[i]))
for (int j = i; j <= 1e7; j += i)
if (!fc[j]) fc[j] = i;
}
struct DSU {
vector<int> comp;
DSU(int n) { comp.assign(n + 5, -1); }
int find(int u) { return comp[u] < 0 ? u : comp[u] = find(comp[u]); }
void unite(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (comp[u] > comp[v]) swap(u, v);
comp[u] += comp[v];
comp[v] = u;
}
bool same(int u, int v) { return find(u) == find(v); }
};
void solve() {
DSU dsu(n);
FOR(i, 1, n) if (szx(x[p[i]]) < 2) x[p[i]].pb(i);
sieve();
FOR(i, 1, 15) cerr << fc[i] << ' ';
cerr << '\n';
vector<int> order(n);
iota(all(order), 1);
sort(all(order), [&](int a, int b) { return p[a] < p[b]; });
vector<array<int, 3>> edges;
FOR(o, 1, n - 1) {
int i = order[o];
bool found = 0;
ROF(j, p[i], max(p[order[o - 1]], p[i] - p[order[0]])) {
for (int k : x[fc[j]]) {
if (k == i) continue;
edges.pb({i, k, p[i] - j});
found = 1;
break; // Không cần vòng for k nữa
}
// if (found) break;
}
if (!found) edges.pb({order[0], i, p[order[0]]});
}
pii prev{-1, -1};
ROF(o, n - 2, 0) {
int i = order[o];
if (p[i] == p[order[o + 1]] && prev.fi != -1) {
edges.pb({i, prev.fi, prev.se});
continue;
}
for (int j = p[i]; j <= p[order[n - 1]]; j += p[i]) {
auto it = lower_bound(all(order), j, [&](int x, int tar) { return p[x] < tar; });
if (it != order.end() && *it == i) it++;
if (it != order.end()) {
// KHÔNG tìm min gì hết, tóm được thằng nào là đẩy luôn cạnh đó vào!
edges.pb({i, *it, p[*it] - j});
}
}
}
sort(all(edges), [&](array<int, 3> A, array<int, 3> B) { return A[2] < B[2]; });
ll ans = 0;
for (array<int, 3> e : edges) {
if (!dsu.same(e[0], e[1])) {
ans += e[2];
dsu.unite(e[0], e[1]);
}
}
cout << ans;
}
void input() {
cin >> n;
FOR(i, 1, n) cin >> p[i];
}
void preprocess() {}
void reset() {}
int main() {
setIO();
openFile("main");
int t = 1;
// cin >> t;
preprocess();
while (t--) {
input();
solve();
reset();
}
}
