题解 | kotori和素因子

#include<bits/stdc++.h>
#include <functional>
using namespace std;
using ll=long long;
const ll inf=1145141919810;
ll n;
vector<ll>a(10);
vector<vector<ll>>q;
ll ans=inf;

const ll N = 1000; // 质数筛选最大范围
vector<ll> primes;         // 存储筛出的所有质数
vector<bool> is_prime(N + 1, true); // 标记是否为质数，初始默认是质数

// 欧拉筛（线性筛）预处理质数
void sieve() {
    is_prime[0] = is_prime[1] = false; // 0和1不是质数
    for (ll i = 2; i <= N; ++i) {   // 遍历2~MAXN所有数
        if (is_prime[i]) {
            primes.push_back(i);       // 未被标记则是质数，加入数组
        }
        for (ll p : primes) {          // 用已筛质数标记合数
            if (i * p > N) break;   // 超出范围则终止
            is_prime[i * p] = false;   // 标记i*p为合数
            if (i % p == 0) break;     // 保证仅被最小质因子标记
        }
    }
}

bool B[N];

void dfs(ll x,ll v){
    for(auto t:q[x]){
        if(B[t]==false){
            if(x<n-1){
                B[t]=true;
                dfs(x+1,v+t);
                B[t]=false;
            }else{
                ans=min(ans,v+t);
            }
        }
    }
    
}


int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    sieve();
    cin>>n;
    
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }

    for(ll i=0;i<n;i++){
        vector<ll>t;
        for(ll j=1;j*j<=a[i];j++){
            if(a[i]%j==0){
                if(is_prime[j]==true)t.emplace_back(j);
                if(is_prime[a[i]/j]==true){
                    t.emplace_back(a[i]/j);
                }
            }
        }
        q.emplace_back(t);
    }
    dfs(0,0);
    if(ans==inf)cout<<-1;
    else cout<<ans;

	return 0;
}