质数（素数），洛谷 P5723

pyzyd

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

1. // #include <bits/stdc++.h>
   
2. #include <iostream>
   
3. #include <vector>
   
4. using namespace std;
   
5. 
   
6. // 求质数数组之和
   
7. int sums(vector<int>& v){
   
8.     int sumv = 0;
   
9.     for (auto i:v){
   
10.         sumv += i;
    
11.     }
    
12.     return sumv;
    
13. }
    
14. 
    
15. // 判断下一个数是否为质数
    
16. bool isPrime(vector<int>&v, int vb){
    
17.     for (auto i:v){
    
18.         if (vb%i == 0){
    
19.             return false;
    
20.         }
    
21.     }
    
22.     return true;// 不能被之前的质数整除，则为质数
    
23. }
    
24. 
    
25. void addPrime(vector<int>& v){
    
26.     int vb = v.back() + 1;//从最后一个质数加1开始
    
27.     vb = vb%2?vb:vb+1;// 质数除了2，都是奇数
    
28.     while(1){
    
29.         if (isPrime(v,vb)){
    
30.             v.push_back(vb);
    
31.             break;// 一次只添加一个质数
    
32.         }
    
33.         vb += 2;// 确保vb为奇数
    
34.     }
    
35. }
    
36. 
    
37. 
    
38. int main(){
    
39.     int L;
    
40.     cin>>L;
    
41.     vector<int> primes = {2};//初始化质数数组,从2开始
    
42.     while (sums(primes) <= L){
    
43.         addPrime(primes);//一次添加一个质数
    
44.     }
    
45.     // 获得的质数数组之和大于L，删除最后一个质数
    
46.     primes.pop_back();
    
47.     for(auto i : primes){
    
48.         cout<<i<<endl;
    
49.     }
    
50.     cout<<primes.size();
    
51.     return 0;
    
52. }

复制代码

继续学习

FishC

您好！关于洛谷 P5723 的质数口袋问题，您提供的代码有一些不完整和逻辑问题。主要问题在于：  
- 在 main 函数中，while 循环条件不完整，且没有处理输出。  
- isPrime 函数效率较低，因为它检查所有已有质数，对于大数可能慢。  
- 添加质数的逻辑可能导致和超过 L，因为它在添加后检查。  

我建议使用更高效的标准方法：逐个数字检查是否为质数（使用平方根优化），并在添加前检查总和是否超过 L。以下是修正后的代码：

1. 
   
2. #include <iostream>
   
3. #include <vector>
   
4. #include <cmath>
   
5. using namespace std;
   
6. 
   
7. // 判断一个数是否为质数
   
8. bool isPrime(int n) {
   
9.     if (n <= 1) return false;
   
10.     if (n == 2) return true;
    
11.     if (n % 2 == 0) return false;
    
12.     for (int i = 3; i * i <= n; i += 2) {
    
13.         if (n % i == 0) return false;
    
14.     }
    
15.     return true;
    
16. }
    
17. 
    
18. int main() {
    
19.     int L;
    
20.     cin >> L;
    
21.     vector<int> primes;
    
22.     int current_sum = 0;
    
23.    
    
24.     // 从2开始逐个检查数字
    
25.     for (int num = 2; ; num++) {
    
26.         if (isPrime(num)) {
    
27.             // 如果添加当前质数会使和超过L，则停止
    
28.             if (current_sum + num > L) {
    
29.                 break;
    
30.             }
    
31.             primes.push_back(num);
    
32.             current_sum += num;
    
33.         }
    
34.     }
    
35.    
    
36.     // 输出质数个数
    
37.     cout << primes.size() << endl;
    
38.     // 输出每个质数，每行一个
    
39.     for (int p : primes) {
    
40.         cout << p << endl;
    
41.     }
    
42.    
    
43.     return 0;
    
44. }
    

复制代码

这个代码直接、高效，且符合题目要求。输出第一行是质数的个数，之后每行输出一个质数。如果您有其他问题，欢迎继续问！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。