洛谷P5723质数口袋题解

题目

题目描述

小A 有一个质数口袋，里面可以装各个质数。他从 2 开始，依次判断各个自然数是不是质数，如果是质数就会把这个数字装入口袋。口袋的负载量就是口袋里的所有数字之和。但是口袋的承重量有限，不能装得下总和超过 L(1\le L\le100000)L(1≤L≤100000) 的质数。给出 LL，请问口袋里能装下几个质数？将这些质数从小往大输出，然后输出最多能装下的质数个数，所有数字之间有一空行。

输入输出样例

输入#1：
100
输出#1：
2
3
4
7
11
13
17
19
23
9

思路

这是一个判断质数的函数。但是在测试时，是出不来结果的。

bool prime(int a){
	if(a==0||a==1){
		return false;
	}
	if(a==2){
		return true;
	}
	for(int i=0;i<a;i++){
		if(a%i==0){
			return false;
		}
	}
	return true;
}

这种情况，在洛谷上应该是RE的。（详情点这里）
很明显，对10进行取余（相当于除以0）

---

这是修改后的代码，没有问题，详细解释请看注释

bool prime(int a){
	if(a==0||a==1){ //对于0，1要特殊判断，否则没有返回值
		return false;
	}
	if(a==2){
		return true;
	}
	for(int i=2;i<a;i++){ //一定从2开始！
		if(a%i==0){ //如果是其他数的倍数，就为合数，直接返回false
			return false;
		}
	}
	return true;
}

完整代码

#include<bits/stdc++.h>
using namespace std;
bool prime(int a){
	if(a==0||a==1){
		return false;
	}
	if(a==2){
		return true;
	}
	for(int i=2;i<a;i++){
		if(a%i==0){
			return false;
		}
	}
	return true;
}
int main(){
	int n,add=0,num=0; //n代表口袋内质数的最大值，add代表当前所有质数的和，num是个数
	cin>>n;
	for(int i=2;;i++){
		if(prime(i)==true && add+i<=n){
			add+=i;
			cout<<i<<endl;
			num++;
		}
		if(add+i>n){ //没有这个判断，无法跳出循环
			break;
		}
	}
	cout <<num;
	return 0;
}

其它

新建博客，点击直达
单独写了一个素数筛法的文章，内容不多，只有最基本的两种，详情点这里
回顾一下上篇学英语的题解，详情点这里