题解 | kotori和素因子

# Process input
n = int(input())
ax = list(map(int, input().split()))

# Functions
def prime_factors(n):
    factors = set()
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            factors.add(d)
            n //= d
        d += 1
    if n > 1:
        factors.add(n)
    return list(factors)

def dfs(arr, i, used, acc):
    if i == len(arr):
        return acc
    factors = prime_factors(arr[i])
    minVal = 99999
    for factor in factors:
        if factor in used:
            continue
        used.add(factor)
        val = dfs(arr, i+1, used, acc+factor)
        used.remove(factor)
        minVal = min(val, minVal)
    return minVal

# Invoke and output
res = dfs(ax, 0, set(), 0)
if res == 99999:
    res = -1
print(res)