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

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. }
    

复制代码

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

跳转到最佳答案楼层