【GESP】C++二级练习 luogu-P5723 【深基4.例13】质数口袋

GESP二级练习，多层循环分支练习，难度★★☆☆☆。

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

题目要求

题目描述

小 A 有一个质数口袋，里面可以装各个质数。他从 $2$ 开始，依次判断各个自然数是不是质数，如果是质数就会把这个数字装入口袋。

口袋的负载量就是口袋里的所有数字之和。

但是口袋的承重量有限，装的质数的和不能超过 $L$。给出 $L$，请问口袋里能装下几个质数？将这些质数从小往大输出，然后输出最多能装下的质数的个数，数字之间用换行隔开。

输入格式

一行一个正整数 $L$。

输出格式

将这些质数从小往大输出，然后输出最多能装下的质数个数。

输入 #1

100

输出 #1

2
3
5
7
11
13
17
19
23
9

输入 #2

5

输出 #2

2
3
2

输入 #3

11

输出 #3

2
3
5
3

说明/提示

数据保证，$1 \le L \le {10}^5$。

---

题目分析

解题思路

1. 首先，我们需要理解题目的核心要求：
   • 从2开始依次判断每个自然数是否为质数
   • 如果是质数，则将其加入口袋（即累加到总和中）
   • 口袋的负载量（所有质数之和）不能超过给定的L值
2. 解题思路：
   • 读取承重上限L
   • 从2开始遍历自然数
   • 对每个数进行质数判断
     • 只需要判断到该数的平方根
     • 如果能被任何小于它的数整除，则不是质数
   • 如果是质数，判断加入后是否超过承重上限
     • 未超过则输出该质数并计数
     • 超过则输出质数个数并结束程序

---

示例代码

#include <cmath>
#include <iostream>
using namespace std;
int main() {
    // 输入口袋承重上限L
    int L;
    cin >> L;
    // 计数器，记录质数个数
    int count = 0;
    // 当前质数和
    int sum = 0;
    // 从2开始遍历数字
    int cur_num = 2;
    while (true) {
        // 假设当前数字是质数
        bool is_prime = true;
        // 对大于3的数进行质数判断
        if (cur_num > 3) {
            // 只需要判断到平方根即可
            for (int i = 2; i <= sqrt(cur_num); i++) {
                // 如果能被整除，则不是质数
                if (cur_num % i == 0) {
                    is_prime = false;
                    break;
                }
            }
        }
        // 如果是质数，尝试放入口袋
        if (is_prime) {
            sum += cur_num;
            // 如果总和未超过承重，则输出该质数
            if (sum <= L) {
                cout << cur_num << endl;
                count++;
            } else {
                // 超过承重则输出质数总数并结束
                cout << count;
                break;
            }
        }
        // 继续检查下一个数
        cur_num++;
    }
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。