#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 1012345678;

struct divisor {
	int x, p;
	bool operator<(const divisor& d) const {
		return p != d.p ? p < d.p : x < d.x;
	}
	bool operator==(const divisor& d) const {
		return p == d.p && x == d.x;
	}
};

vector<pair<int, int> > prime_factorization(int n) {
	vector<pair<int, int> > res;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			int cnt = 0;
			do {
				n /= i;
				cnt++;
			} while (n % i == 0);
			res.push_back({i, cnt});
		}
	}
	if (n >= 2) {
		res.push_back({n, 1});
	}
	return res;
}

vector<divisor> find_divisors(int n) {
	vector<pair<int, int> > factors = prime_factorization(n);
	vector<divisor> res;
	res.push_back(divisor{1, 0});
	for (pair<int, int> i : factors) {
		vector<divisor> nres;
		for (divisor d : res) {
			int mul = 1;
			for (int j = 0; j <= i.second; j++) {
				nres.push_back(divisor{d.x * mul, d.p + j});
				mul *= i.first;
			}
		}
		res = nres;
	}
	sort(res.begin(), res.end());
	return res;
}

int solve(int N, const vector<int>& A) {
	// step #1. merge divisors
	vector<vector<divisor> > divs(N);
	vector<int> factors(N);
	int Z = 0;
	for (int i = 0; i < N; i++) {
		divs[i] = find_divisors(A[i]);
		factors[i] = divs[i].back().p;
		if (int(divs[i].size()) > N) {
			divs[i].resize(N);
		}
		Z += divs[i].size();
	}
	vector<divisor> all_divs(Z);
	Z = 0;
	for (int i = 0; i < N; i++) {
		for (divisor d : divs[i]) {
			all_divs[Z++] = d;
		}
	}
	sort(all_divs.begin(), all_divs.end());
	all_divs.erase(unique(all_divs.begin(), all_divs.end()), all_divs.end());
	Z = all_divs.size();

	// step #2. make graph
	vector<vector<int> > G(N);
	for (int i = 0; i < N; i++) {
		for (divisor d : divs[i]) {
			int pos = lower_bound(all_divs.begin(), all_divs.end(), d) - all_divs.begin();
			G[i].push_back(pos);
		}
	}

	// step #3. maximum matching
	vector<int> match1(N, -1);
	vector<int> match2(Z, -1);
	for (int i = 0; i < N; i++) {
		vector<bool> vis(N, false);
		vector<int> par(N, -1);
		auto find_augment = [&](auto& self, int pos) -> int {
			vis[pos] = true;
			int res = INF;
			for (int j : G[pos]) {
				if (match2[j] == -1) {
					if (res > j) {
						res = j;
						par[pos] = j;
					}
				} else if (!vis[match2[j]]) {
					int subres = self(self, match2[j]);
					if (res > subres) {
						res = subres;
						par[pos] = j;
					}
				}
			}
			return res;
		};
		find_augment(find_augment, i);
		vector<int> path;
		int cur = i;
		while (cur != -1) {
			path.push_back(cur);
			cur = par[cur];
			path.push_back(cur);
			cur = match2[cur];
		}
		for (int i = 0; i < int(path.size()); i += 2) {
			match1[path[i]] = path[i + 1];
			match2[path[i + 1]] = path[i];
		}
	}

	// step #4. compute answer
	int ans = 0;
	for (int i = 0; i < N; i++) {
		ans += factors[i] - all_divs[match1[i]].p;
	}

	return ans;
}

int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	int ans = solve(N, A);
	cout << ans << endl;
	return 0;
}