kotori和素因子

package main

/* 
    计算并存储每个数的所有素因子
    dfs遍历所有可能
 */

import (
	"fmt"
	"math"
)

// 判断一个数是否为素数
func isPrime(x int) bool {
	if x < 2 {
		return false
	}
	for i := 2; i <= int(math.Sqrt(float64(x))); i++ {
		if x%i == 0 {
			return false
		}
	}
	return true
}

// 获取一个数的所有素因子
func getPrimeFactors(x int) []int {
	factors := []int{}
	for i := 2; i <= x; i++ {
		if x%i == 0 && isPrime(i) {
			factors = append(factors, i)
			// 跳过所有i的倍数
			for x%i == 0 {
				x /= i
			}
		}
	}
	return factors
}

func main() {
	var n int
	fmt.Scanf("%d", &n)

	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &a[i])
	}

	// 为每个数获取所有可能的素因子
	primeFactors := make([][]int, n)
	for i, num := range a {
		primeFactors[i] = getPrimeFactors(num)
	}

	// 尝试所有可能的素因子组合，使用回溯法
	used := make([]bool, 10000) // 假设素因子不超过10000
	minSum := math.MaxInt32

	var backtrack func(index, sum int)
	backtrack = func(index, sum int) {
		if index == n {
			if sum < minSum {
				minSum = sum
			}
			return
		}

		for _, factor := range primeFactors[index] {
			if !used[factor] {
				used[factor] = true
				backtrack(index+1, sum+factor)
				used[factor] = false
			}
		}
	}

	backtrack(0, 0)

	if minSum == math.MaxInt32 {
		fmt.Println(-1)
	} else {
		fmt.Println(minSum)
	}
}

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
}