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

解题思路

从 2 起顺序检查质数。发现质数时，若加入后超过 L 就结束，否则加入总和、输出并计数。

正确性说明

按从小到大顺序装入与题目过程一致。首个装不下的质数出现时题目过程停止，已输出的正是全部装入的质数。

易错点

判断平方根时包含等号；1 不是质数；计数最后单独一行。题面空行表述与样例不一致，这里按样例逐行输出。

复杂度

枚举上界 L，试除实现时间 O(L√L)，空间 O(1)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int L;
    cin >> L;
    int sum = 0, count = 0;
    for (int x = 2; x <= L; x++) {
        bool prime = true;
        for (int d = 2; d * d <= x; d++)
            if (x % d == 0) {
                prime = false;
                break;
            }
        if (prime) {
            if (sum + x > L)
                break;
            sum += x;
            count++;
            cout << x << "\n";
        }
    }
    cout << count << "\n";
    return 0;
}