质数（素数），洛谷 P5723
P5723 【深基4.例13】质数口袋 - 洛谷// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
// 求质数数组之和
int sums(vector<int>& v){
int sumv = 0;
for (auto i:v){
sumv += i;
}
return sumv;
}
// 判断下一个数是否为质数
bool isPrime(vector<int>&v, int vb){
for (auto i:v){
if (vb%i == 0){
return false;
}
}
return true;// 不能被之前的质数整除，则为质数
}
void addPrime(vector<int>& v){
int vb = v.back() + 1;//从最后一个质数加1开始
vb = vb%2?vb:vb+1;// 质数除了2，都是奇数
while(1){
if (isPrime(v,vb)){
v.push_back(vb);
break;// 一次只添加一个质数
}
vb += 2;// 确保vb为奇数
}
}
int main(){
int L;
cin>>L;
vector<int> primes = {2};//初始化质数数组,从2开始
while (sums(primes) <= L){
addPrime(primes);//一次添加一个质数
}
// 获得的质数数组之和大于L，删除最后一个质数
primes.pop_back();
for(auto i : primes){
cout<<i<<endl;
}
cout<<primes.size();
return 0;
}
继续学习{:10_265:}
您好！关于洛谷 P5723 的质数口袋问题，您提供的代码有一些不完整和逻辑问题。主要问题在于：
- 在 main 函数中，while 循环条件不完整，且没有处理输出。
- isPrime 函数效率较低，因为它检查所有已有质数，对于大数可能慢。
- 添加质数的逻辑可能导致和超过 L，因为它在添加后检查。
我建议使用更高效的标准方法：逐个数字检查是否为质数（使用平方根优化），并在添加前检查总和是否超过 L。以下是修正后的代码：
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 判断一个数是否为质数
bool isPrime(int n) {
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) return false;
}
return true;
}
int main() {
int L;
cin >> L;
vector<int> primes;
int current_sum = 0;
// 从2开始逐个检查数字
for (int num = 2; ; num++) {
if (isPrime(num)) {
// 如果添加当前质数会使和超过L，则停止
if (current_sum + num > L) {
break;
}
primes.push_back(num);
current_sum += num;
}
}
// 输出质数个数
cout << primes.size() << endl;
// 输出每个质数，每行一个
for (int p : primes) {
cout << p << endl;
}
return 0;
}
这个代码直接、高效，且符合题目要求。输出第一行是质数的个数，之后每行输出一个质数。如果您有其他问题，欢迎继续问！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]