[NOIP 2002 普及组] 选数

题意

给定 n 个整数，从中选出 k 个数求和。问有多少种选择方式，使得选出的数字之和是素数。

思路

n <= 20，可以直接枚举所有组合。

Python 中：

python

1combinations(numbers, k)

会产生所有“不关心顺序、选 k 个”的方案。对每个方案求和，然后用试除法判断是否为素数。

判断素数时只需要试除到 sqrt(x)。为了避免浮点误差，用 math.isqrt(x) 得到整数平方根。

Python 知识

itertools.combinations(numbers, k) 直接枚举所有选 k 个数的组合。
sum(chosen) 可以对一个元组求和。
math.isqrt(x) 返回 floor(sqrt(x))，适合写整数素数判断。
把素数判断写成 is_prime 函数，可以让主流程更清楚。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/itertools_recipes.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22from itertools import combinations
from math import isqrt


def is_prime(x):
    if x < 2:
        return False
    for factor in range(2, isqrt(x) + 1):
        if x % factor == 0:
            return False
    return True


n, k = map(int, input().split())
numbers = list(map(int, input().split()))

answer = 0
for chosen in combinations(numbers, k):
    if is_prime(sum(chosen)):
        answer += 1

print(answer)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72/**
 * Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

/* P1036 [NOIP 2002 普及组] 选数 */
/* DFS 枚举选 k 个数的所有组合，求和并判断是否为素数。 */

/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, k;
int a[MAXN];       // 输入数组
int choose[MAXN];  // choose[i] = 1 表示选了第 i 个数
int ans;

// 判断 x 是否为素数
bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

// dfs(dep, cnt) 表示处理到第 dep 个数，已经选了 cnt 个
void dfs(int dep, int cnt) {
    if (dep == n + 1) {
        if (cnt == k) {
            int sum = 0;
            for (int i = 1; i <= n; i++) {
                if (choose[i]) sum += a[i];
            }
            if (is_prime(sum)) ans++;
        }
        return;
    }

    // 剪枝：剩余的数全选也不够 k 个
    if (cnt + (n - dep + 1) < k) return;

    // 不选第 dep 个数
    choose[dep] = 0;
    dfs(dep + 1, cnt);

    // 选第 dep 个数
    choose[dep] = 1;
    dfs(dep + 1, cnt + 1);
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    dfs(1, 0); // 从第 1 个数开始，已选 0 个
    cout << ans << "\n";
    return 0;
}

复杂度

一共有 $\binom{n}{k}$ 个组合。设最大组合和为 $S$ ，素数判断为 $O(\sqrt S)$ ，总时间复杂度为 $O(\binom{n}{k}\sqrt S)$ 。空间复杂度为 $O(k)$ 。

总结

这题是学习 combinations 的典型题：题目说“任选 k 个，不分顺序”，就可以直接映射到组合枚举。

[NOIP 2002 普及组] 选数

目录

题意

思路

Python 知识

代码

复杂度

总结