打鸡血

题目描述

小猴特别喜爱质数，他从好友小美那里借来了n（n≤10）张卡片，每张卡片上有一个数ci（1-1000）。小猴从中选择若干张卡片（至少1张），如果这些数的和是质数他会像被打了鸡血一样，马上做10个俯卧撑10个仰卧起坐10个深蹲... 他想知道，有多少中卡片的选法可以让他进入打鸡血状态？（只要卡片是不一样的，哪怕数相同，也算不同的选法）

请你利用程序，帮助他计算一下。

输入描述

输入共2行：

第1行，1个正整数n。

第2行，n个正整数c1，c2，c3，...，cn，以英文逗号隔开。

输出描述

一个正整数，表示总共的选法数量

样例输入

4

7,11,13,17

样例输出

7

代码详解

展开查看

n = int(input())
c = [int(i) for i in input().split(",")]
use = [False for i in range(n)]
cnt = 0

def isPrime(x):
    if x <= 1:
        return False
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

def dfs(step):
    global n,c,use,cnt
    if step>=n:
        to = 0
        for i in range(n):
            if use[i] == True:
                to += c[i]
        if isPrime(to):
            cnt += 1
        return
    use[step] = False
    dfs(step + 1)
    use[step] = True
    dfs(step + 1)

dfs(0)
print(cnt)

运行结果

展开查看

4
7,11,13,17
7