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

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求从 $2$ ~2~ 开始依次把质数装入“质数口袋”，装入的质数之和不能超过 $L$ ~L~，在此前提下使装入的质数个数最多，最后按从小到大的顺序输出装入的质数并输出个数。核心解法是用筛法预处理出所有不超过 $L$ ~L~ 的质数，再按升序贪心累加，直到加上下一个质数会超过 $L$ ~L~ 为止。

分析

核心观察

质数是按升序依次装入口袋的，所以任意一个可行方案都对应质数序列的一个前缀，要让个数最多就必须优先装入最小的质数。设不超过 $L$ ~L~ 的质数从小到大为 $p_1 < p_2 < \cdots < p_m$ ~p_1 < p_2 < \cdots < p_m~，则对任意 $k$ ~k~ 而言，前 $k$ ~k~ 个质数之和是所有大小为 $k$ ~k~ 的质数集合中和最小者。

思路

由核心观察可知，能装下 $k$ ~k~ 个质数当且仅当

$\displaystyle p_1 + p_2 + \cdots + p_k \le L$

因此答案就是使该不等式成立的最大整数 $k$ ~k~。由于质数严格递增，前缀和也严格递增，只需从最小的质数开始逐个试加：维护当前已装入的和 $S$ ~S~ 与个数 $k$ ~k~，遇到质数 $p$ ~p~ 时若 $S + p \le L$ ~S + p \le L~ 就把它装入口袋，否则立即停止，因为后面更大的质数只会让和超出更多。

质数的筛选方式决定了整体复杂度。朴素做法对每个数单独试除判断质数，单次判定需要 $O(\sqrt{n})$ ~O(\sqrt{n})~ 时间，总复杂度为 $O(L\sqrt{L})$ ~O(L\sqrt{L})~，在本题范围内虽可接受但不必要；改用埃氏筛只需 $O(L \log \log L)$ ~O(L \log \log L)~ 时间就能一次性筛出全部质数，之后顺序扫描一遍即可完成贪心，贪心的正确性由核心观察保证。

具体示例

以 $L = 100$ ~L = 100~ 为例，从最小的质数开始依次累加：

$\displaystyle 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 = 100$

此时和恰好等于 $100$ ~100~，仍满足“不超过 $L$ ~L~”的限制；下一个质数是 $29$ ~29~，而 $100 + 29 = 129 > 100$ ~100 + 29 = 129 > 100~，超出承重量，于是停止装入。最终装入的质数为 $2, 3, 5, 7, 11, 13, 17, 19, 23$ ~2, 3, 5, 7, 11, 13, 17, 19, 23~ 共 $9$ ~9~ 个，先逐行输出这 $9$ ~9~ 个质数，再输出个数 $9$ ~9~。

算法步骤

读入 $L$ ~L~。
建立标记数组 isPrime 并全部置为真，再把下标 $0$ ~0~ 与下标 $1$ ~1~ 置为假。
从 $2$ ~2~ 开始枚举 i，当 $i^2 > L$ ~i^2 > L~ 时结束；若 isPrime[i] 为真，则把 $i^2$ ~i^2~ 到 $L$ ~L~ 之间所有 i 的倍数标记为假。
初始化累加和 total 与计数 cnt 均为 $0$ ~0~，从 $2$ ~2~ 到 $L$ ~L~ 顺序枚举 i。
若 isPrime[i] 为假则跳过；对质数 i，若 $total + i > L$ ~total + i > L~ 则结束枚举，否则输出 i，令 total 加上 i、cnt 加 $1$ ~1~。
输出 cnt。

复杂度分析

时间： $O(L \log \log L)$ ~O(L \log \log L)~，埃氏筛标记合数的代价，贪心扫描为 $O(L)$ ~O(L)~，被筛法代价吸收。
空间： $O(L)$ ~O(L)~，布尔标记数组的长度为 $L + 1$ ~L + 1~。

实现注意事项

$L = 1$ ~L = 1~ 时没有任何质数能装入口袋，此时不输出任何质数，只输出个数 $0$ ~0~ 这一行，不能因为个数是 $0$ ~0~ 而漏掉输出。
筛法必须把下标 $0$ ~0~ 与下标 $1$ ~1~ 显式标记为非质数， $1$ ~1~ 既不是质数也不是合数，不能沿用初始值。
停止条件是 $total + i > L$ ~total + i > L~ 而非 $total + i \ge L$ ~total + i \ge L~：和恰好等于 $L$ ~L~ 时仍然可以装入。
输出共 $cnt + 1$ ~cnt + 1~ 行，前 $cnt$ ~cnt~ 行是装入的质数，最后一行是质数个数，每个数字各占一行并以换行结尾。
累加和按构造始终不超过 $L \le 10^5$ ~L \le 10^5~，用 $32$ ~32~ 位整数存放即可；标记数组需要长度为 $L + 1$ ~L + 1~，否则访问下标 $L$ ~L~ 时会越界。
埃氏筛内层循环从 $i^2$ ~i^2~ 开始标记，因为小于 $i^2$ ~i^2~ 的倍数已被更小的质数标记过，从 $i^2$ ~i^2~ 开始可以省去重复工作。

源代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int L;
    cin >> L;

    vector<bool> isPrime(L + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= L; ++i) {
        if (!isPrime[i]) {
            continue;
        }
        for (int j = i * i; j <= L; j += i) {
            isPrime[j] = false;
        }
    }

    int total = 0, cnt = 0;
    for (int i = 2; i <= L; ++i) {
        if (!isPrime[i]) {
            continue;
        }
        if (total + i > L) {
            break;
        }
        total += i;
        ++cnt;
        cout << i << '\n';
    }

    cout << cnt << '\n';
    return 0;
}

import sys


def main():
    data = sys.stdin.read().split()
    L = int(data[0])

    is_prime = [True] * (L + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(L ** 0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * i, L + 1, i):
            is_prime[j] = False

    total = 0
    cnt = 0
    out = []
    for i in range(2, L + 1):
        if not is_prime[i]:
            continue
        if total + i > L:
            break
        total += i
        cnt += 1
        out.append(str(i))
    out.append(str(cnt))
    sys.stdout.write("\n".join(out) + "\n")


main()

目前没有评论。