A80487.质数口袋 题解

因为题目中我们并不需要特别大的质数（只关心前若干个连续质数的和 ≤ L），所以可以这样做：

从 i = 2i=2 开始逐个判断是否为质数；
判断时只需试除到 \sqrt{i}
如果是质数，则尝试加入“口袋”；
加入前先判断：sum + i <= L？
是 → 加入，输出，计数+1
否 → 直接 break（不能再装了）
继续下一个数
这样既保证了顺序性，又避免了不必要的计算。​
；

代码详见：

#include <iostream>
#include <cmath>
using namespace std;


bool isPrime(int x) {
    if (x < 2) return false;
    if (x == 2) return true;
    if (x % 2 == 0) return false;
    for (int i = 3; i * i <= x; i += 2) {
        if (x % i == 0)
            return false;
    }
    return true;
}

int main() {
    int L;
    cin >> L;

    int sum = 0, count = 0;
    int i = 2;

    while (true) {
        if (isPrime(i)) {
            if (sum + i > L) break; 

            cout << i << endl;
            sum += i;
            count++;
        }
        i++;
    }

    cout << count << endl;
    return 0;
}

感谢阅读