【python】选数

题目：

"""

题目描述：

给定一个由 n 个整数组成的序列x_1, x_2,..., x_n)，以及一个整数 k ( k < n )。从这 n 个整数中选择 k 个整数相加，可以得到多种不同的和。例如，当 n = 4，k = 3，且这四个整数分别为 3，7，12，19时，所有可能的组合及其对应的和为：

- 3 + 7 + 12 = 22

- 3 + 7 + 19 = 29

- 7 + 12 + 19 = 38

- 3 + 12 + 19 = 34

任务是计算出有多少种不同的组合，使得这些组合的和是一个素数。例如，在上述例子中，仅有一种组合的和是素数：3 + 7 + 19 = 29。

输入格式：

- 每个测试文件只包含一组测试数据。

- 每组测试数据的第一行包含两个整数 n 和 k (1 <= n <= 20，k < n)。

- 第二行包含 n 个整数 x_1, x_2,..., x_n ) (1<=x_i<=5000000)。

输出格式：

- 对于每组输入数据，输出一个整数，表示满足条件的组合数量。

"""

代码：

# 判断一个数是否为素数
def is_prime(num):
    if num <= 1:  # 如果数小于等于1，不是素数
        return False
    # 只需要检查到数的平方根，因为如果num有因数，它必定至少有一个不大于其平方根
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:  # 如果num能被任何小于它的平方根的数整除，不是素数
            return False
    return True  # 如果没有找到因数，那么num是素数
 
 
# 生成数组arr中所有可能的k元素组合
def generate_combinations(arr, n, k):
    result = []  # 用于存储所有组合的列表
 
    # 辅助递归函数，用于生成组合
    def generate_combinations_util(current, start):
        # 如果当前组合的长度等于k，则将其添加到结果列表中
        if len(current) == k:
            # 创建 current 列表的一个副本 append的是一个列表
            result.append(current.copy())
            return
 
        # 递归地从数组中选择不同的元素，以构建组合
        for i in range(start, n):
            current.append(arr[i])  # 将元素加入当前组合
            # util实用程序
            generate_combinations_util(current, i + 1)  # 递归调用
            current.pop()  # 移除刚才加入的元素，以便于下一次循环添加新的元素
 
    generate_combinations_util([], 0)  # 调用辅助函数
    return result  # 返回所有组合
 
 
# 读取输入
n, k = map(int, input().split())  # 读取n和k
a = list(map(int, input().split()))  # 读取数组a
count = 0  # 用于计数满足条件的组合数量
 
# 获取所有可能的组合
combinations = generate_combinations(a, n, k)
 
# 遍历每一个组合
for combo in combinations:
    # 如果组合的和是素数
    if is_prime(sum(combo)):
        count += 1  # 计数增加
 
# 输出满足条件的组合总数
print(count)