已知 n n n 个整数 x 1 , x 2 , ? ? , x n x_1,x_2,\cdots,x_n x1?,x2?,?,xn?,以及 1 1 1 个整数 k k k( k < n k<n k<n)。从 n n n 个整数中任选 k k k 个整数相加,可分别得到一系列的和。例如当 n = 4 n=4 n=4, k = 3 k=3 k=3, 4 4 4 个整数分别为 3 , 7 , 12 , 19 3,7,12,19 3,7,12,19 时,可得全部的组合与它们的和为:
3 + 7 + 12 = 22 3+7+12=22 3+7+12=22
3 + 7 + 19 = 29 3+7+19=29 3+7+19=29
7 + 12 + 19 = 38 7+12+19=38 7+12+19=38
3 + 12 + 19 = 34 3+12+19=34 3+12+19=34
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数: 3 + 7 + 19 = 29 3+7+19=29 3+7+19=29。
第一行两个空格隔开的整数 n , k n,k n,k( 1 ≤ n ≤ 20 1 \le n \le 20 1≤n≤20, k < n k<n k<n)。
第二行 n n n 个整数,分别为 x 1 , x 2 , ? ? , x n x_1,x_2,\cdots,x_n x1?,x2?,?,xn?( 1 ≤ x i ≤ 5 × 1 0 6 1 \le x_i \le 5\times 10^6 1≤xi?≤5×106)。
输出一个整数,表示种类数。
4 3
3 7 12 19
1
【题目来源】
NOIP 2002 普及组第二题
from itertools import combinations
import math
def judge(num):
if num<=1:
return False
for i in range(2,int(math.sqrt(num))+1):
if num%i==0:
return False
return True
if __name__=="__main__":
n, m = map(int, input().split())
mapp = list(map(int, input().split()))
value_ans = 0
for item in combinations(mapp, m):
value_key = 0
for j in range(len(item)):
value_key += item[j]
# print(value_key)
if judge(value_key):
# print(value_key)
value_ans += 1
print(value_ans)
本题目用到了tertools库中的combinations函数。来自 itertools 模块的函数 combinations(list_name, x) 将一个列表和数字 ‘x’ 作为参数,并返回一个元组列表,每个元组的长度为 ‘x’,其中包含x个元素的所有可能组合。列表中元素不能与自己结合,不包含列表中重复元素。这样可以得到从n个数中选取m个数的所有组合。其按照元组的方式储存。遍历的时候当成列表遍历即可。再就是素数的判断,遍历的时候考虑到开方优化的方案时要记得加1,因为这里的范围是左闭右开的。对于组合数的函数运用刷完题单后会进行总结一下