# 素因子/质因子:能整除给定正整数的质数 # 质数/素数:一个大于1的自然数,除了1和它本身外,不能被其他自然数整除 from collections import deque from math import inf n = int(input()) a = list(map(int, input().split())) # 首先我们要找出每一个数的所有素因子 def factor(x:int): if x<2: return set() fac = set() while x%2 == 0: fac.add(2) x //= 2 f = 3 while f*f <=x: if x%f == 0: fac.add(f) x //= f else: f += 2 if x > 1: fac.add(x) return list(fac) # 函数逻辑: # 将x/2直到不能整除为止,此时x的因子只包含奇数 # 如果x小于f*f # 那么x一定是(f-2)*(f-2)到f*f范围内的质数 # 为什么?因为如果它不是质数,那么x=a*b,其中a、b都为奇数,而且a,b都>=f # 如果比f小,那么在之前的循环里就整除了 # 因为a,b都>=f,所以x>=f*f,与条件矛盾 # 所以x一定是质数 # 但是在整除偶数的过程中,可能会出现1,所以要加条件x>1,比如x=4 b = [] for num in a: b.append(factor(num)) # 用DFS min_sum = inf def f(index,current_sum,visited): global min_sum # **这两个if的顺序 if current_sum >= min_sum: return if index == n: min_sum = current_sum return for num in b[index]: if current_sum+num > min_sum: # ** break # ** if num not in visited: visited.add(num) f(index+1,current_sum+num,visited) # ** current_sum+num放在函数内 visited.discard(num) return min_sum if min_sum!=inf else -1 print(f(0,0,set()))