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

· · 题解

题意

给定和的范围，求最多有多少个从小到大且不重复的质数相加<=和的范围。

思路

暴力+优化，其实这样不会TLE，所以还是挺水的一道题。我用一个函数来做质数判断。

上代码！（具体注释在代码里）

#include<iostream>
#include<cmath>//要用sqrt函数
using namespace std;
int l,ans=0,cnt=1,sum=0,a[100010];//l是和的范围，ans是最多能装多少个质数，cnt是辅助a数组存入质数的计数器，a数组就是用来存质数的一个质数表。
int zhishu(int n){//判断是否是质数的函数。
    if(n==2||n==3||n==5||n==7||n==11||n==13){//判断，如果没有那么下面的优化就是错的，因为它会把上面的数全部算成合数。（实在看不懂可以自己举几个例子）
        return 1;
    }
    if(n%2==0||n%3==0||n%5==0||n%7==0||n%11==0||n%13==0||n==1){//优化，n=1也要return 0。
        return 0;
    }
    for(int i=2;i<=sqrt(n);i++){//判断，判断一个数是否是质数只要判断到它的开方就可以了。
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}
int main(){
    cin>>l;
    for(int i=1;;i++){//不用写i<=多少，到时候直接break就可以了。
        if(zhishu(i)==1){
            a[cnt]=i;//用cnt辅助存储质数
            sum+=i;//用和帮助判断是否越界
            ans++;//总质数数量++
            cnt++;//计数器++;
        }
        if(sum>l){//如果越界
            sum-=i;减掉使它越界的质数
            a[cnt]=0;//在质数表里删掉它
            cnt-=2;//这里一定要减2，因为cnt初始=1，当1加完了cnt就变成了2，2加完了cnt就变成了3，以此类推。实在没看懂的可以举几个例子。
            ans--;//总质数数量--
            break;//跳出
        }
    }
    for(int i=1;i<=cnt;i++){//打印质数表
        cout<<a[i]<<endl;
    }
    cout<<ans<<endl;//输出总质数数量
    return 0;//拜拜！
}