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

解题思路

从 $2$ 开始递增枚举整数，判断质数。若当前质数加入后不超过 $L$，就输出并累加；否则立即停止。最后输出计数。

正确性说明

算法严格按从小到大的质数顺序处理。停止前每个质数都能加入，停止时最小的下一个质数已无法加入，因此不跳过前面质数的前提下数量达到最大。

复杂度分析

在本题范围内直接试除足够快。若枚举到 $K$，复杂度约为 $O(K\sqrt K)$，空间 $O(1)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
bool prime(int x){if(x<2)return false;for(int i=2;1LL*i*i<=x;i++)if(x%i==0)return false;return true;}
int main(){
    int L,sum=0,cnt=0;cin>>L;
    for(int x=2;;x++) if(prime(x)){
        if(sum+x>L) break;
        cout<<x<<'\n';sum+=x;cnt++;
    }
    cout<<cnt<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; bool prime(int x){if(x<2)return false;for(int i=2;1LLii<=x;i++)if(x%i==0)return false;return true;} int main(){ int L,sum=0,cnt=0;cin>>L; for(int x=2;;x++) if(prime(x)){ if(sum+x>L) break; cout<<x<<'\n';sum+=x;cnt++; } cout<<cnt<<'\n';return 0; }