【洛谷】P5723 【深基4.例13】质数口袋_洛谷 p5723

题目来源

P5723 【深基4.例13】质数口袋 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

小 A 有一个质数口袋，里面可以装各个质数。他从 2 开始，依次判断各个自然数是不是质数，如果是质数就会把这个数字装入口袋。

口袋的负载量就是口袋里的所有数字之和。

但是口袋的承重量有限，装的质数的和不能超过 L。给出 L，请问口袋里能装下几个质数？将这些质数从小往大输出，然后输出最多能装下的质数的个数，数字之间用换行隔开。

输入格式

一行一个正整数 L。

输出格式

将这些质数从小往大输出，然后输出最多能装下的质数个数，所有数字之间有一空行。

说明/提示

1≤L≤10^5.

分析＆思路

这道题并不是很难。首先，我们需要定义几个变量，然后用一个for循环来遍历。个人认为，本题唯一的难点在于如何判断质数。我的思路是先写一个循环，让他循环10^5（10万）次，在循环里先判断这个数加上下一个数是不是大于这个L，如果不是，再执行。然后再定义一个布尔类型的变量来进行判断。里面再套一个循环，从2开始，如果自己乘自己不大于这个数，就进行判断：如果外层循环的数模（%）自己等于0，那么说明这个数有因数，将布尔变量改为false，如果不是，再次进行循环，直到退出循环。如果直到退出循环这个数依然为true，即为质数，输出，并将答案的个数++。思路捋清了，就开始写吧。

#include<bits/stdc++.h>
using namespace std;
int l,ans,sum;//定义，l为总体，ans为答案（即个数），sum为计数器
int main()
{
    cin>>l;//先输入范围
    return 0;
}

然后来执行循环，循环10万次，并加上判断。

#include<bits/stdc++.h>
using namespace std;
int l,ans,sum;//定义，l为总体，ans为答案（即个数），sum为计数器
int main()
{
    cin>>l;//先输入范围
    for(int i=2;i<=10000;i++)//循环十万次（为什么从2开始？因为2是最小的质数）
    {
        if(sum+i<=l)//如果计数器加上下一个数不超出l这个范围，执行接下来的语句
        {
        }
    }
    return 0;
}

接下来定义bool变量

#include<bits/stdc++.h>
using namespace std;
int l,ans,sum;//定义，l为总体，ans为答案（即个数），sum为计数器
int main()
{
    cin>>l;//先输入范围
    for(int i=2;i<=10000;i++)//循环十万次（为什么从2开始？因为2是最小的质数）
    {
        if(sum+i<=l)//如果计数器加上下一个数不超出l这个范围，执行接下来的语句
        {
            bool zs = true;//定义一个名为zs（质数）的bool变量，让它等于true（默认是质数）
            
        
            
        }
    }
    return 0;
}

然后，通过另一个循环嵌套来进行判断这个数有没有因数。

#include<bits/stdc++.h>
using namespace std;
int l,ans,sum;//定义，l为总体，ans为答案（即个数），sum为计数器
int main()
{
    cin>>l;//先输入范围
    for(int i=2;i<=10000;i++)//循环十万次（为什么从2开始？因为2是最小的质数）
    {
        if(sum+i<=l)//如果计数器加上下一个数不超出l这个范围，执行接下来的语句
        {
            bool zs = true;//定义一个名为zs（质数）的bool变量，让它等于true（默认是质数）
            for (int j=2;j*j<=i;j++)//二层循环。j*j<=i是避免2和3这两个质数
			{
            	if (i%j==0)//如果i有因数
				{
                	zs = false;//zs设为否（即合数）
                	break;//退出循环
            	}
        	}
            
        }
    }
    return 0;
}

最后，进行最后一个判断，判断是否为质数，若是，输出。

#include<bits/stdc++.h>
using namespace std;
int l,ans,sum;//定义，l为总体，ans为答案（即个数），sum为计数器
int main()
{
    cin>>l;//先输入范围
    for(int i=2;i<=10000;i++)//循环十万次（为什么从2开始？因为2是最小的质数）
    {
        if(sum+i<=l)//如果计数器加上下一个数不超出l这个范围，执行接下来的语句
        {
            bool zs = true;//定义一个名为zs（质数）的bool变量，让它等于true（默认是质数）
            for (int j=2;j*j<=i;j++)//二层循环。j*j<=i是避免2和3这两个质数
			{
            	if (i%j==0)//如果i有因数
				{
                	zs = false;//zs设为否（即合数）
                	break;//退出循环
            	}
        	}
            if (zs) {//因为zs默认为true（质数），所以如果不是false（合数），就会执行判断下的语句
            	cout<<i<<endl;//输出这个数
            	sum+=i;//计数器等于前面的数加上这个数
            	ans++;//次数也要加
        	}
            
        }
    }
    return 0;
}

at last，输出最终的答案。

#include<bits/stdc++.h>
using namespace std;
int l,ans,sum;//定义，l为总体，ans为答案（即个数），sum为计数器
int main()
{
    cin>>l;//先输入范围
    for(int i=2;i<=10000;i++)//循环十万次（为什么从2开始？因为2是最小的质数）
    {
        if(sum+i<=l)//如果计数器加上下一个数不超出l这个范围，执行接下来的语句
        {
            bool zs = true;//定义一个名为zs（质数）的bool变量，让它等于true（默认是质数）
            for (int j=2;j*j<=i;j++)//二层循环。j*j<=i是避免2和3这两个质数
			{
            	if (i%j==0)//如果i有因数
				{
                	zs = false;//zs设为否（即合数）
                	break;//退出循环
            	}
        	}
            if (zs) {//因为zs默认为true（质数），所以如果不是false（合数），就会执行判断下的语句
            	cout<<i<<endl;//输出这个数
            	sum+=i;//计数器等于前面的数加上这个数
            	ans++;//次数也要加
        	} 
        }
    }
	cout<<ans;//输出共有几个数
    return 0;
}

AC代码

#include<bits/stdc++.h>
using namespace std;
int l,ans,sum;
int main()
{
    cin>>l;
    for(int i=2;i<=10000;i++)
    {
    	if(sum+i<=l)
    	{
    		bool zs = true;
        	for (int j=2;j*j<=i;j++) 
			{
            	if (i%j==0) 
				{
                	zs = false;
                	break;
            	}
        	}
        	if (zs) {
            	cout<<i<<endl;
            	sum+=i;
            	ans++;
        	}
		}
	}
	cout<<ans;
    return 0;
}
 

结果

好吧，又是一道水题