题解 | kotori和素因子

# 素因子/质因子：能整除给定正整数的质数
# 质数/素数：一个大于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()))