【深基4.例13】质数口袋

题意

从 2 开始依次考虑自然数。如果一个数是质数，就尝试把它放进口袋。

口袋中所有质数的和不能超过 L。要求按从小到大的顺序输出能放下的所有质数，最后再输出质数个数。

思路

关键是两件事：

从小到大枚举候选数；
只在“加入这个质数后总和仍然不超过 L”时，才真正把它加入答案。

判断质数时，只需要试除到 sqrt(x)。如果 x 有一个大于 sqrt(x) 的因子，那么它必然还有一个小于 sqrt(x) 的配对因子，所以前面已经会被发现。

循环条件写成：

text

1while total + candidate <= limit:

这里的 candidate 是当前自然数。即使它不是质数，循环里也会继续向后找；如果它是质数，则检查加入后是否超重。

这题的朴素想法就是按题意枚举和试除，Python 教学版不额外创建 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：本题输出多行答案，可以先把字符串放入列表，最后 "\n".join(...) 一次输出。
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md：math.isqrt(x) 返回整数平方根，避免浮点误差。
range(3, isqrt(x) + 1, 2) 只枚举奇数因子，跳过所有偶数。
primes.append(str(candidate)) 提前转成字符串，是为了最后能直接用 join 拼接输出。

代码

python

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
31from math import isqrt


def is_prime(x):
    if x < 2:
        return False
    if x == 2:
        return True
    if x % 2 == 0:
        return False

    for d in range(3, isqrt(x) + 1, 2):
        if x % d == 0:
            return False
    return True


limit = int(input())

total = 0
candidate = 2
primes = []

while total + candidate <= limit:
    if is_prime(candidate):
        total += candidate
        primes.append(str(candidate))
    candidate += 1

primes.append(str(len(primes)))
print("\n".join(primes))

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/**
 * 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;

// 判断 x 是否是质数（试除法，只需检查到 sqrt(x)）
bool is_prime(int x) {
    if (x < 2) return false;
    if (x == 2) return true;
    if (x % 2 == 0) return false;
    for (int d = 3; d * d <= x; d += 2) {
        if (x % d == 0) return false;
    }
    return true;
}

int main() {
    int L;        // 口袋容量上限
    int total = 0; // 已放入质数的和
    int primes[1005]; // 存储能放入的质数
    int cnt = 0;     // 质数个数
    cin >> L;
    // 从 2 开始逐个检查自然数
    for (int candidate = 2; total + candidate <= L; candidate++) {
        if (is_prime(candidate)) {
            total += candidate;
            primes[cnt++] = candidate;
        }
    }
    // 输出所有质数
    for (int i = 0; i < cnt; i++) {
        cout << primes[i] << endl;
    }
    cout << cnt << endl; // 最后一行输出质数个数
    return 0;
}

Pythonic 写法

质数筛选累加：

python

1
2
3
4
5
6
7
8
9def is_prime(x):
    return x>1 and all(x%d for d in range(2,int(x**0.5)+1))
L=int(input()); s=0; ps=[]
for p in range(2,10**9):
    if is_prime(p):
        if s+p>L: break
        ps.append(p); s+=p
print(*ps, sep='\n')
print(len(ps))

复杂度

设最终检查到的最大候选数为 m。每个候选数试除到平方根，时间复杂度可以粗略看作 $O(m\sqrt m)$ ；在 L <= 10^5 的范围内足够。空间复杂度是 $O(c)$ ，其中 c 是输出的质数个数。

总结

本题把“质数判断”和“累计容量限制”放在一起考察。实现时要先判断是不是质数，再判断加入后是否超过 L。

【深基4.例13】质数口袋

目录

题意

思路

Python 知识

代码

Pythonic 写法

复杂度

总结