质数口袋

洛谷·深入浅出 · 代码 · cpp · 难度 3/5 · 共 642 字

从小到大装质数，和不超 L，输出各质数与个数

洛谷
例题

正文

// 原题：https://oj.yecheng.tv/p/1382
// 题意：从 2 起依次把质数装入口袋，装到再加下一个就超过 L 为止；输出装入的每个质数（每行一个）及质数个数。
// 思路：从小到大枚举质数，能装（sum+p<=L）就装并输出，超过 L 立即停止；最后输出计数。
// 复杂度：O(L log L) 量级。
// 易错点：判满即停；最后单独输出个数；数字之间用换行隔开，不要多打空行。
#include <iostream>
using namespace std;
bool isprime(int x){
    if(x < 2) return false;
    for(int i = 2; i * i <= x; i++) if(x % i == 0) return false;
    return true;
}
int main(){
    int L;
    cin >> L;
    int sum = 0, cnt = 0;
    for(int p = 2; ; p++){
        if(!isprime(p)) continue;
        if(sum + p > L) break;
        sum += p;
        cnt++;
        cout << p << endl;
    }
    cout << cnt << endl;
    return 0;
}

质数口袋

正文

洛谷·深入浅出的其它内容