[已解决]牛客求素数个数

lsmCC

1. #include <iostream>
   
2. using namespace std;
   
3. int main()
   
4. {
   
5.     int t,n;
   
6.     cin>>t;
   
7.     int a[t],b[t];
   
8.     for(int i=0;i<t;i++)
   
9.     {
   
10.         cin>>a[i];
    
11.         b[i]=0;
    
12.         
    
13.     }
    
14.     for(int i=0;i<t;i++)
    
15.     {   //要确保是那组数据
    
16. 
    
17.     for(int c=2;c<=a[i];c++)
    
18.     {
    
19.         int flag=0;
    
20.         for(int j=2;j<i;j++)
    
21.         {
    
22.             if(c%j==0)
    
23.             {
    
24.                 flag=1;
    
25.                 break;
    
26.             }
    
27. 
    
28.         }
    
29.         if(flag==0)
    
30.         {
    
31.             b[i]++;
    
32.         }
    
33.     }
    
34.     }
    
35. 
    
36. for(int i=0;i<t;i++)
    
37. {
    
38.     cout<<b[i];
    
39. }
    
40. return 0;
    
41.                
    
42.         
    
43. }

复制代码

答案是4为什么求出来9啊，还有如果不用数组是不是没有跟更简便的写法

最佳答案

月排行榜 / 总排行榜

isdkz

2023-10-7 12:14:11

问题出在第二个循环中的内层循环条件判断中。在判断是否为素数时，应该将内层循环的条件改为 j<=sqrt(c) ，而不是 j<i 。另外，也可以将内层循环的起始值改为2，而不是1。

修正后的代码如下：

1. #include <iostream>
   
2. #include <cmath>
   
3. using namespace std;
   
4. 
   
5. int main()
   
6. {
   
7.     int t, n;
   
8.     cin >> t;
   
9.     int a[t], b[t];
   
10.     for (int i = 0; i < t; i++)
    
11.     {
    
12.         cin >> a[ i];
    
13.         b[ i] = 0;
    
14.     }
    
15.     for (int i = 0; i < t; i++)
    
16.     {
    
17.         for (int c = 2; c <= a[ i]; c++)
    
18.         {
    
19.             int flag = 0;
    
20.             for (int j = 2; j <= sqrt(c); j++)
    
21.             {
    
22.                 if (c % j == 0)
    
23.                 {
    
24.                     flag = 1;
    
25.                     break;
    
26.                 }
    
27.             }
    
28.             if (flag == 0)
    
29.             {
    
30.                 b[ i]++;
    
31.             }
    
32.         }
    
33.     }
    
34. 
    
35.     for (int i = 0; i < t; i++)
    
36.     {
    
37.         cout << b[ i];
    
38.     }
    
39.     return 0;
    
40. }
    

复制代码

关于不使用数组的简便写法，可以直接在计算素数的过程中进行统计，而不需要使用额外的数组来存储结果。

1. #include <iostream>
   
2. #include <cmath>
   
3. using namespace std;
   
4. 
   
5. int main()
   
6. {
   
7.     int t, n;
   
8.     cin >> t;
   
9.     for (int i = 0; i < t; i++)
   
10.     {
    
11.         cin >> n;
    
12.         int count = 0;
    
13.         for (int c = 2; c <= n; c++)
    
14.         {
    
15.             int flag = 0;
    
16.             for (int j = 2; j <= sqrt(c); j++)
    
17.             {
    
18.                 if (c % j == 0)
    
19.                 {
    
20.                     flag = 1;
    
21.                     break;
    
22.                 }
    
23.             }
    
24.             if (flag == 0)
    
25.             {
    
26.                 count++;
    
27.             }
    
28.         }
    
29.         cout << count;
    
30.     }
    
31.     return 0;
    
32. }
    

复制代码

这样就可以直接在内层循环中统计素数的个数，而不需要使用额外的数组来存储结果。

跳转到最佳答案楼层

isdkz

问题出在第二个循环中的内层循环条件判断中。在判断是否为素数时，应该将内层循环的条件改为 j<=sqrt(c) ，而不是 j<i 。另外，也可以将内层循环的起始值改为2，而不是1。

修正后的代码如下：

1. #include <iostream>
   
2. #include <cmath>
   
3. using namespace std;
   
4. 
   
5. int main()
   
6. {
   
7.     int t, n;
   
8.     cin >> t;
   
9.     int a[t], b[t];
   
10.     for (int i = 0; i < t; i++)
    
11.     {
    
12.         cin >> a[ i];
    
13.         b[ i] = 0;
    
14.     }
    
15.     for (int i = 0; i < t; i++)
    
16.     {
    
17.         for (int c = 2; c <= a[ i]; c++)
    
18.         {
    
19.             int flag = 0;
    
20.             for (int j = 2; j <= sqrt(c); j++)
    
21.             {
    
22.                 if (c % j == 0)
    
23.                 {
    
24.                     flag = 1;
    
25.                     break;
    
26.                 }
    
27.             }
    
28.             if (flag == 0)
    
29.             {
    
30.                 b[ i]++;
    
31.             }
    
32.         }
    
33.     }
    
34. 
    
35.     for (int i = 0; i < t; i++)
    
36.     {
    
37.         cout << b[ i];
    
38.     }
    
39.     return 0;
    
40. }
    

复制代码

关于不使用数组的简便写法，可以直接在计算素数的过程中进行统计，而不需要使用额外的数组来存储结果。

1. #include <iostream>
   
2. #include <cmath>
   
3. using namespace std;
   
4. 
   
5. int main()
   
6. {
   
7.     int t, n;
   
8.     cin >> t;
   
9.     for (int i = 0; i < t; i++)
   
10.     {
    
11.         cin >> n;
    
12.         int count = 0;
    
13.         for (int c = 2; c <= n; c++)
    
14.         {
    
15.             int flag = 0;
    
16.             for (int j = 2; j <= sqrt(c); j++)
    
17.             {
    
18.                 if (c % j == 0)
    
19.                 {
    
20.                     flag = 1;
    
21.                     break;
    
22.                 }
    
23.             }
    
24.             if (flag == 0)
    
25.             {
    
26.                 count++;
    
27.             }
    
28.         }
    
29.         cout << count;
    
30.     }
    
31.     return 0;
    
32. }
    

复制代码

这样就可以直接在内层循环中统计素数的个数，而不需要使用额外的数组来存储结果。

Mike_python小

你的代码存在两个问题。

首先，在第二个 for 循环中，判断素数的内层循环应该是从 2 到根号下 c，而不是 j<i。这是因为判断素数只需要检查是否能整除到根号下 c 即可。

其次，在计算素数个数 b[i] 时，应该将这一行放在外层循环的最后，而不是内层循环。否则，每次内层循环遇到非素数时都会执行 b[i]++，导致计数错误。

以下是修正问题后的代码：

2. #include <iostream>
3. #include <cmath>
4. using namespace std;
6. int main() {
7.     int t, n;
8.     cin >> t;
10.     int a[t], b[t];
11.     for (int i = 0; i < t; i++) {
12.         cin >> a[i];
13.         b[i] = 0;
14.     }
16.     for (int i = 0; i < t; i++) {
17.         for (int c = 2; c <= a[i]; c++) {
18.             int flag = 0;
19.             for (int j = 2; j <= sqrt(c); j++) {
20.                 if (c % j == 0) {
21.                     flag = 1;
22.                     break;
23.                 }
24.             }
25.             if (flag == 0) {
26.                 b[i]++;
27.             }
28.         }
29.     }
31.     for (int i = 0; i < t; i++) {
32.         cout << b[i] << endl;
33.     }
35.     return 0;
36. }

复制代码

关于是否可以简化代码，如果你想得到素数个数而不需要存储每个测试用例的结果，可以直接输出计数 b[i] 的值，而不使用数组 b[]。这样可以节省空间。另外，可以注意到一个优化的点是在判断素数时，只需要从 2 到根号下 a[i] 的范围内判断即可，无需遍历到 a[i]。

希望能解决你的问题！如果还有其他疑问，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！