题解 | kotori和素因子

n=int(input())
a=[int(i) for i in input().split()]
from functools import lru_cache

@lru_cache(None)
def is_prime(x):#x>=2
    if x<=3:
        return True
    if x%2==0:
        return False
    limit=int(x**0.5) #只试除奇数到sqrt(x)
    for num in range(3,limit+1,2):
        if x%num==0:
            return False
    return True


used=set()
min_sum=float('inf')
def dfs(index, cur_sum):
    global min_sum
    if cur_sum>=min_sum:
        return
    if index==n:
        min_sum=cur_sum
        return 
    x=a[index]
    for num in range(2,x+1):
        if x%num==0 and (num not in used) and is_prime(num):
            used.add(num)
            dfs(index+1,cur_sum+num)
            used.remove(num)


dfs(0,0)
print(-1 if min_sum==float('inf') else min_sum)