解题思路

1、输入数据，获得数组a，并得到数组a中的最大值，记为maxa。

2、使用欧拉筛，计算 2到maxa的所有素数。

3、计算数组a中每个元素的素因子列表。

4、暴力枚举，递归+回溯，求最优解。

思路明确的话，写代码没有什么难度，就不做赘述了，下面详细讨论下素数的筛法。

素数的筛法

1、埃氏筛法（埃拉托斯特尼筛法，Sieve of Eratosthenes）

该筛法的核心思想是从 2 开始，将每个素数的倍数标记为合数，逐步筛选出所有素数。具体来说，先假设所有数都是素数，然后从最小的素数 2 开始，把 2 的倍数（除 2 本身）都标记为合数；接着找到下一个未被标记的数，它就是素数，再把它的倍数标记为合数，依此类推，直到遍历完所有小于等于给定范围的数。

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

vector<int> prime; //素数集合
const int N = 10000;

int main() {
    //埃氏筛法求素数
    vector<bool> isP(N + 1, true);
    for (int i = 2; i <= N; ++i) {
        if (isP[i]) {
            prime.push_back(i);
            for (int j = i * i; j <= N; j += i) {
                isP[j] = false;
            }
        }
    }
}

埃氏筛法简单易懂，总结起来就是把所有素数的倍数全部标记为合数。

缺点是许多合数会有重复标记的问题，时间复杂度没有到最优。比如数字30，会被2、3、5分别标记一次。

2、欧拉筛法，或可称为线性筛法（Sieve of Eratosthenes with Linear Time Complexity）

该算法真正做到了每个合数只被标记一次。

其核心思想是，每个合数可以分解为其最小素因数和另一个数的乘积。依然拿数字30举例：30 = 2 * 15 = 3 * 10 = 5 * 6。其存在多种分解方式，但30的最小素因数是2，因此我们希望它只在 2 * 15的时候被标记一次。

有了这样的觉悟，我们再考虑怎么写代码。

很显然，我们不能像埃氏筛那样，只在出现新的素数时去标记其倍数作为合数了，而是必须对循环中的每一个数（无论素数还是合数），都去进行小范围的合数标记。

问题来了，这里的小范围，究竟有多小呢？

举个例子，假设现在循环到数字15，我们要标记一些15的倍数为合数，那么可选的数字有

30 = 2 * 15

45 = 3 * 15

60 = 4 * 15

75 = 5 * 15

……

很明显60 = 4 * 15 不能选，因为4是合数，还可以继续分解为 2 * 2，即60 = 2 * 30，我们应该在循环到数字30的时候去筛。也就是说，我们只考虑该数字乘以素数的情况。

那么75可以吗？显然也不行，75的最小素因子是3，即75 = 3 * 25，应该在循环到数字25的时候去筛。

正确的做法是，标记完30和45就停止。

再举个例子，假设现在循环到数字9，我们要标记一些9的倍数为合数，那么可选的数字有

18 = 2 * 9，27 = 3 * 9。到此停止，因为下一个45 = 5 * 9的最小素因子是3，45 = 3 * 15，该在循环到15时进行标记。

看到这里，聪明的小伙伴应该已经懂了。

对于任意一个数字k，我们依次将k和已有的每个素数p相乘，标记得到的k * p为合数。当k能被p整除时，跳出循环。

下面给出cpp代码。

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

vector<int> prime; //素数集合
int ans = 10000;

void dfs(vector<vector<int>> &pf, vector<int> &select, vector<bool> &flag) {
    int n = select.size();
    if(n == pf.size()) {
        int res = 0;
        for(int &i : select) {
            res += prime[i];
        }
        if(ans > res) ans = res;
        return;
    }
    for(int &i : pf[n]) {
        if(flag[i]) continue;
        flag[i] = true;
        select.push_back(i);
        dfs(pf, select, flag);
        select.pop_back();
        flag[i] = false;
    }
}

int main() {
    int n, maxa = 0;
    cin >> n;
    vector<int> a(n);
    for (int& i : a) {
        cin >> i;
        if (i > maxa) maxa = i;
    }
    //欧拉筛求素数
    vector<bool> isP(maxa + 1, true);
    for (int i = 2; i <= maxa; ++i) {
        if (isP[i]) prime.push_back(i);
        for (int j = 0; j < prime.size() && i * prime[j] <= maxa; ++j) {
            isP[i * prime[j]] = false;
            if (i % prime[j] == 0) break; //这一句是精髓
        }
    }
    //计算a中每个数的素因数
    vector<vector<int>> pf(n);
    for (int i = 0; i < n; ++i) {
        int k = a[i];
        for (int j = 0; k != 1; ++j) {
            if (k % prime[j]) continue;
            pf[i].push_back(j);
            do {
                k /= prime[j];
            } while (k % prime[j] == 0);
        }
    }
    //暴力枚举
    vector<int> select;
    vector<bool> flag(prime.size(), false);
    dfs(pf, select, flag);
    cout << (ans == 10000 ? -1 : ans);
}
// 64 位输出请用 printf("%lld")