专业的河南网站建设公司排名,成都专业seo公司,404 重定向 wordpress,网址域名大全题目#xff1a; 题目描述#xff1a; 给定一个由 n 个整数组成的序列x_1, x_2,..., x_n)#xff0c;以及一个整数 k ( k n )。从这 n 个整数中选择 k 个整数相加#xff0c;可以得到多种不同的和。例如#xff0c;当 n 4#xff0c;k 3#…题目 题目描述 给定一个由 n 个整数组成的序列x_1, x_2,..., x_n)以及一个整数 k ( k n )。从这 n 个整数中选择 k 个整数相加可以得到多种不同的和。例如当 n 4k 3且这四个整数分别为 371219时所有可能的组合及其对应的和为 - 3 7 12 22 - 3 7 19 29 - 7 12 19 38 - 3 12 19 34 任务是计算出有多少种不同的组合使得这些组合的和是一个素数。例如在上述例子中仅有一种组合的和是素数3 7 19 29。 输入格式 - 每个测试文件只包含一组测试数据。 - 每组测试数据的第一行包含两个整数 n 和 k (1 n 20k n)。 - 第二行包含 n 个整数 x_1, x_2,..., x_n ) (1x_i5000000)。 输出格式 - 对于每组输入数据输出一个整数表示满足条件的组合数量。 代码
# 判断一个数是否为素数
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 Falsereturn 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)