kotori和素因子

import collections
class Solution():
    def __init__(self, alist, n):
        self.alist = alist
        self.n = n
        self.res = float('+inf')
        self.dic = collections.defaultdict(list)
        self.no_repeat_set = set()

    def is_prime(self, x):
        if x <= 1:
            return False
        for i in range(2, x):
            if x % i == 0:
                return False
        return True
    
    def dfs(self, idx, s):
        if idx == self.n:
            self.res = min(self.res, s)
            return
        for prime_factor in self.dic[self.alist[idx]]:
            if prime_factor not in self.no_repeat_set:
                self.no_repeat_set.add(prime_factor)
                self.dfs(idx+1, s+prime_factor)
                self.no_repeat_set.remove(prime_factor)
    
    def func(self):
        if self.n <= 0:
            return -1
        for ele in self.alist:
            if ele == 1:
                return -1
            for i in range(2, ele+1):
                if self.is_prime(i) and ele % i == 0:
                    self.dic[ele].append(i)
            if self.dic[ele] == []:
                return -1
        self.dfs(0, 0)
        return -1 if self.res == float('+inf') else self.res


n = int(input().strip())
alist = list(map(int, input().strip().split()))
solution = Solution(alist, n)
print(solution.func())

#include <bits/stdc++.h>

using namespace std;
#define int long long

int n, a[15], sushu[15], res = 0, ans = 0x3f3f3f3f, flag = 0;

//判断是不是素数
int isprime(int x) {
    for (int i = 2; i <= sqrt(x); ++i) {
        if (x % i == 0) {
            return 0;
        }
    }
    return 1;
}

void dfs(int u) {
    if (u == n) {
        ans = min(res, ans);
        flag = 1;
        return;
    }
    //先求出所有素因子
    for (int i = 2; i <= a[u]; ++i) {
        if (a[u] % i == 0 && isprime(i)) {
            //满足条件，入
            int f = 0;
            for (int j = 0; j <= u; ++j) {
                if (sushu[j] == i) {
                    f = 1;
                }
            }
            if (f == 0) {
                sushu[u] = i;
                res += i;
                dfs(u + 1);
                sushu[u] = 0;
                res -= i;
            }
        }
    }
}

signed main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    dfs(0);
    if (flag == 0) {
        cout << -1;
        return 0;
    }
    cout << ans;
    return 0;
}

#include <climits>
#include <iostream>
#include <vector>
#include<cmath>
#include<algorithm>
#include<numeric>
using namespace std;

void dfs(int x, vector<int>& su) {
    int flag = 0;
    int a = sqrt(x);
    for (int i = 2; i <= a; i++) {
        if (!(x % i)) {
            dfs(x / i, su);
            dfs(i, su);
            flag++;
        }
    }
    if (!flag && !count(su.begin(), su.end(), x)) {
        su.push_back(x);
    }
    return;
}

void ddfs(int n, vector<vector<int>>& su, vector<int>& choose,vector<int>& val) {
    if(choose.size()==su.size()) {
        val.push_back(accumulate(choose.begin(),choose.end(),0));
        return;
    }
    for (int i = 0; i < su[n].size(); i++) {
        if (!count(choose.begin(), choose.end(), su[n][i])) {
            choose.push_back(su[n][i]);
            ddfs(n+1, su, choose, val);
            choose.pop_back();
        }
    }
    return;
}

int minadd(vector<vector<int>>& su) {
    vector<int> choose;
    vector<int> val;
    ddfs(0, su, choose, val);
    if (val.empty()) return -1;
    return *min_element(val.begin(), val.end());
}

int main() {
    int n = 0, m = 0;
    cin >> n;
    vector<vector<int>> su(n, vector<int>(0));
    for (int i = 0; i < n; i++) {
        cin >> m;
        dfs(m, su[i]);
    }
    cout << minadd(su) << endl;
    return 0;
}

package main

import (
    "fmt"
    "math"
)

func main() {
    var n int
    fmt.Scan(&n)
    arr:=make([][]int,n)
    var x int
    for i:=0;i<n;i++{
        fmt.Scan(&x)
        tmp:=make_arr(x)
        arr[i]=tmp
    }
    // fmt.Printf("%v\n",arr)
    min:=math.MaxInt32
    vis:=map[int]bool{}
    var dfs func(int,int)
    dfs=func(j int,sum int){
        if j==n{
            if sum<min{
                min=sum
            }
            return
        }
        for i:=0;i<len(arr[j]);i++{
            x:=arr[j][i]
            if _,ok:=vis[x];ok{
                continue
            }
            sum+=x
            vis[x]=true
            dfs(j+1,sum)
            sum-=x
            delete(vis,x)
        }
    }
    dfs(0,0)
    if min==math.MaxInt32{
        fmt.Println(-1)
        return
    }
    fmt.Println(min)
}

func make_arr(x int)[]int{
    ans:=[]int{}
    for i:=2;i<=x;i++{
        if x%i==0&&check(i){
            ans=append(ans,i)
        }
    }
    return ans
}

func check(x int)bool{
    for i:=2;i<x;i++{
        if x%i==0{
            return false
        }
    }
    return true
}

import java.util.*;
public class Main {
//定义存放的list的list(因为list中数组长度可变),用来存放每个数的素因子
    static List<List<Integer>> list = new ArrayList<List<Integer>>();
    static int deepth = 0;//深度，也就是正整数的个数；
    static int minRes = 10000;//返回的结果
    static int[] vis = new int[1000];//因为每个访问的数都不重复，所以vis[i]指i是否被访问过
    static int sum = 0;//搜索时的和
    static boolean flag = false; //flag为1说明已经找到了最小值（遍历到了最底层（说明每个数都有素因子，只要有一个数没有，则无法递归到最底层））
//先找到每个数的素因子，然后再深度搜索满足条件的最小值，若不存在，则输出-1
//判断是否为素数
    public static boolean isSu(int n) {
        if (n == 1) {
            return false;
        }
        //从2开始到根号n之间，只要找到n可以除尽的数，说明n有其他因子，则n不是素数
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

//找素因子,n为输入的数，x为在list中存放的位置(第几行)
    public static void prime(int n, int x) {
        List<Integer> tempList = new ArrayList<Integer>();
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                if (isSu(i)) {
                    tempList.add(i); //满足素数，则存入
                }
                //还要存对应的另外一个因子（因为只遍历到根号n），前提是另外一个因子和此因子不相等，且也为素数
                if (i * i != n && isSu(n / i)) {
                    tempList.add(n / i);
                }
            }
        }
        list.add(tempList);
    }

//深度搜索:y为第几层
    public static void dfs(int y) {
        if (y == deepth) { //如果遍历深度到最底层，退出，只能往回找了
            flag = true;//此时说明每一层都有素因子，合法的，一定会有最小值
            minRes = Math.min(minRes, sum);
            return;
        }
        for (int i = 0; i < list.get(y).size(); i++) {
            if (vis[list.get(y).get(i)] == 0) { //说明没有被访问
                sum += list.get(y).get(i);
                vis[list.get(y).get(i)] = 1;//标记为已访问
                dfs(y + 1);//开始遍历下一层;
                vis[list.get(y).get(i)] = 0;//遍历后回溯要先将该点标记为未访问
                sum -= list.get(y).get(i);//标为未读后要将该点的值去掉
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        deepth = Integer.parseInt(in.nextLine());
        String[] res = in.nextLine().split(" ");
        //获取每一个数的素因子，放入list中
        for (int i = 0; i < deepth; i++) {
            prime(Integer.parseInt(res[i]), i);
        }
        //开始从第一层深度搜索
        dfs(0);
        //输出结果
        if (!flag) {
            System.out.println("-1");
        } else {
            System.out.println(minRes);
        }
    }
}