题解 | kotori和素因子 DFS 因数

import itertools


def get_prime_factors(num):
    factors=set()
    i=2
    while i*i<=num:  # 只需要检查到  sqrt(num)
        while num%i==0: # 整除
            factors.add(i)
            num=num//i  #  不断除以当前质数
        i=i+1
    # 关键步骤 处理剩余的质数    num>1 说明剩余的num 是一个质数 无法被2-sqrt(num) 之间的任何数整除
    if num>1:
        factors.add(num)
    return factors
def dfs(arr:list):
    result=[]
    # 定义行
    rows=len(arr)
    def dfs_helper(row,path):
        if rows==row:
            result.append(path.copy())
            return 
        # 遍历这行每个元素    
        for num in arr[row]:
            path.append(num)
            dfs_helper(row+1,path)
            path.pop()
    dfs_helper(0,[])
    return result

def   func():
    n =  int(input())
    a=list(map(int,input().split()))
    prime_factors_list=[]  #所有数的素数 因子
    for num in a:
        factors=get_prime_factors(num)
        prime_factors_list.append(factors)
    # 设置最小值
    min_sum =float('inf')
    # 使用dfs
    res=dfs(prime_factors_list)
    #print("pr",prime_factors_list)
    #print("res",res )
    #for combinations in itertools.product(*prime_factors_list):
    for  combinations in res:
        if len(set(combinations))==n:
            current_sum =sum(combinations)
            if min_sum>current_sum:
                min_sum=current_sum
    ret = min_sum if min_sum!=float('inf') else -1
    print(ret)

func()