题解 | #kotori和素因子#

#include<iostream>

#include<set>

using namespace std;

int n;

int a[1010];

int INF = 1e8;

int sum;

bool primer(int x){

    for(int i = 2; i * i <= x; i ++){

        if(x % i == 0){

            return false;

        }

    }

    return true;

}

// x正在处理的正整数的索引12 15 28 22

// s已经选择的集合 temp当前路径下选择的素因子和

void dfs(int x, set<int> s, int temp){

    if(x == n){

        sum = min(sum, temp);

        return;

    }

    for(int i = 2; i <= a[x]; i ++){

        // 比如12 % 2 == 0 并且2是素数 且未被访问过

        if(a[x] % i == 0 && primer(i) && !s.count(i)){

            // 当插入一个重复的元素 set会忽略 并不会报错

            // 这也是为什么会用set而不是vector的原因

            // 并且它可以自动排序

            s.insert(i); //加入2

            dfs(x + 1, s, temp + i);

            s.erase(i); // 释放掉2

        }

    }

}

int main(){

    sum = INF;

    cin >> n;

    for(int i = 0; i < n; i ++) cin >> a[i];

    set<int> s; // 用来保存已经选中的素因子

    dfs(0, s, 0);

    if(sum == 1e8) cout << -1 << endl;

    else cout << sum << endl;

    return 0;

}