题解 | #kotori和素因子#

import sys
import copy

"""
定义L2接收素因子列表
"""
L2 = []
n = int(input())
numbers = list(map(int, input().split()))


def isprime(x):
    """
    判断x是否为素数
    """
    if x == 2:
        return True
    i = 2
    while i < x:
        if x % i == 0:
            return False
        i += 1
        return True


def suyinzi(x):
    """
    先判断i是否是x的因子,然后判断是否是素数,如果是说明是x的素因子,加入到L中,并去重
    """
    L = []
    i = 2
    while i < x:
        if x % i == 0:
            x = int(x / i)
            if isprime(i):
                L.append(i)
        else:
            i += 1
    L.append(x)
    L = list(set(L))
    L.sort()
    return L


# 遍历整数，求出每个整数的素因子
for x in numbers:
    L2.append(suyinzi(x))

L = copy.deepcopy(L2)
#print(L)
L2 = []


for x in L:
    for element in x:
        if element not in L2:
            L2.append(element)

#递归的初始状态为以下，depth是深度，代表进入到第几个整数的素因子选择
sum = 0
visited = [False for i in range(len(L2))]
depth = 0
res = []


def dfs(L, L2, visited, sum, depth, res):
    '''
    每进入一层，就选择一个数字，当进入到最后一层，停止递归
    '''

    if depth == n:
        res.append(sum)
        return

    for i in L[depth]:
        #如果在本层没有找到未被访问的素因子，那停止递归返回-1
        if visited[L2.index(i)] == False:
            sum += i
            depth += 1
            visited[L2.index(i)] = True
            #进入递归，深度＋1，更新了visited数组，保证没有重复的素因子被选择
            dfs(L, L2, visited, sum, depth, res)
            #回朔
            sum -= i
            depth -= 1
            visited[L2.index(i)] = False
    
    return res


res = dfs(L, L2, visited, sum, depth, res)
if not res:
    print("-1")
else:
    print(min(res))