题解 | kotori和素因子

#include<bits/stdc++.h>
#include <vector>
using namespace std;
#define int long long
const int MAX_SIZE=1000;
vector<bool> pre(MAX_SIZE,true);
vector<int>prenum;
int allans=-1;
void pre_make(){
    
    for(int i=2;i<MAX_SIZE;i++){
        if(pre[i]){
            for(int j=2;j*i<MAX_SIZE;j++){
                pre[i*j]=false;
            }
        }
    }
    for(int i=2;i<MAX_SIZE;i++){
        if(pre[i]){
            prenum.push_back(i);
        }
    }
}
void dfs(vector<int>m,set<int>ans,int pos){
    if(pos==m.size()){
        int t=0;
         for(auto it:ans){
            t+=it;
         }
        if(allans==-1){
            allans=t;
        }else if(allans>t){
            allans=t;
        } 

    }
    int t=m[pos];
    for(int i=0;prenum[i]<=t;i++){
        if(t%prenum[i]==0){
            if(ans.find(prenum[i])==ans.end()){
                 ans.insert(prenum[i]);
                dfs(m,ans,pos+1);
                ans.erase(prenum[i]);
            }
           
        }
    }

}
signed main(){
    pre_make();
    int n;
    cin>>n;
    vector<int>m;
    for(int i=0;i<n;i++){
        int temp;
        cin>>temp;
        m.push_back(temp);

    }
    set<int>ans;
    dfs(m,ans,0);
    cout<<allans<<endl;
}
// 64 位输出请用 printf("%lld")

首先找出题目要求范围内所以所有素数，本代码采用欧拉筛法收集素数，再用dfs对每个数进行枚举如果符合条件在检测ans(set)里是否有该数然后进行递归即可