题解 | #kotori和素因子#

kotori和素因子

https://www.nowcoder.com/practice/7b1c858a3e7a41ed8364178979eaae67

递归
#include <bits/stdc++.h>
using namespace std;

int n;
int a[1010];//正整数的值
int mi=1e9;
//判断是否为质数
bool primer(int x){
   for(int i=2;i*i<=x;i++){
       if(x%i==0){
           return false;
       }
   }
    return true;
}
void dfs(int x,set<int> s,int temp){
    if(x==n){
        mi=min(mi,temp);
        return;
    }
    for(int i=2;i<=a[x];i++){
        if(a[x]%i==0 && primer(i)&&!s.count(i)){
            s.insert(i);
            dfs(x+1,s,temp+i);
            s.erase(i);
        }
    }
}
int  main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    set<int> s;
    dfs(0,s,0);
    if(mi==1e9)cout<<-1;
    else cout<<mi;
    return 0;
    
}


全部评论

相关推荐

点赞 评论 收藏
分享
评论
10
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务