题解 | kotori和素因子

def is_prime(number):
    """
    判断一个数是否为质数
    Args:
        number: 需要判断的数字
    Returns:
        bool: 是否为质数
    """
    if number < 2:
        return False

    # 只需要检查到平方根即可
    for divisor in range(2, int(number ** 0.5) + 1):
        if number % divisor == 0:
            return False

    return True


def find_minimum_prime_factors_sum(
    current_index, used_factors, current_sum, numbers, min_sum
):
    """
    使用深度优先搜索找出每个数的一个质因子，使得这些质因子互不相同且和最小
    Args:
        current_index: 当前处理的数字索引
        used_factors: 已使用的质因子集合
        current_sum: 当前已选质因子的和
        numbers: 输入的数字列表
        min_sum: 当前找到的最小和
    Returns:
        int: 找到的最小和，如果无解则返回float('inf')
    """
    # 基础情况：所有数字都已处理完
    if current_index == len(numbers):
        return min(min_sum, current_sum)

    current_number = numbers[current_index]

    # 尝试当前数字的所有可能质因子
    for factor in range(2, current_number + 1):
        if (
            current_number % factor == 0
            and is_prime(factor)
            and factor not in used_factors
        ):

            # 选择这个质因子
            used_factors.add(factor)
            min_sum = find_minimum_prime_factors_sum(
                current_index + 1, used_factors, current_sum + factor, numbers, min_sum
            )
            # 回溯：移除这个质因子
            used_factors.remove(factor)

    return min_sum


def main():
    """
    主函数：处理输入并输出结果
    """
    # 读取输入
    n = int(input())
    numbers = list(map(int, input().split()))

    # 初始化参数
    used_factors = set()
    initial_min_sum = float("inf")

    # 执行搜索
    result = find_minimum_prime_factors_sum(
        0, used_factors, 0, numbers, initial_min_sum
    )

    # 输出结果
    if result == float("inf"):
        print(-1)
    else:
        print(result)



main()