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

lsmCC

#include <iostream>
using namespace std;
int main()
{
    int t,n;
    cin>>t;
    int a[t],b[t];
    for(int i=0;i<t;i++)
    {
        cin>>a[i];
        b[i]=0;
        
    }
    for(int i=0;i<t;i++)
    {   //要确保是那组数据

    for(int c=2;c<=a[i];c++)
    {
        int flag=0;
        for(int j=2;j<i;j++)
        {
            if(c%j==0)
            {
                flag=1;
                break;
            }

        }
        if(flag==0)
        {
            b[i]++;
        }
    }
    }

for(int i=0;i<t;i++)
{
    cout<<b[i];
}
return 0;
               
        
}

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

最佳答案

月排行榜 / 总排行榜

isdkz

2023-10-7 12:14:11

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

修正后的代码如下：

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int t, n;
    cin >> t;
    int a[t], b[t];
    for (int i = 0; i < t; i++)
    {
        cin >> a[ i];
        b[ i] = 0;
    }
    for (int i = 0; i < t; i++)
    {
        for (int c = 2; c <= a[ i]; c++)
        {
            int flag = 0;
            for (int j = 2; j <= sqrt(c); j++)
            {
                if (c % j == 0)
                {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0)
            {
                b[ i]++;
            }
        }
    }

    for (int i = 0; i < t; i++)
    {
        cout << b[ i];
    }
    return 0;
}

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

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int t, n;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> n;
        int count = 0;
        for (int c = 2; c <= n; c++)
        {
            int flag = 0;
            for (int j = 2; j <= sqrt(c); j++)
            {
                if (c % j == 0)
                {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0)
            {
                count++;
            }
        }
        cout << count;
    }
    return 0;
}

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

跳转到最佳答案楼层

isdkz

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

修正后的代码如下：

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int t, n;
    cin >> t;
    int a[t], b[t];
    for (int i = 0; i < t; i++)
    {
        cin >> a[ i];
        b[ i] = 0;
    }
    for (int i = 0; i < t; i++)
    {
        for (int c = 2; c <= a[ i]; c++)
        {
            int flag = 0;
            for (int j = 2; j <= sqrt(c); j++)
            {
                if (c % j == 0)
                {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0)
            {
                b[ i]++;
            }
        }
    }

    for (int i = 0; i < t; i++)
    {
        cout << b[ i];
    }
    return 0;
}

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

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int t, n;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> n;
        int count = 0;
        for (int c = 2; c <= n; c++)
        {
            int flag = 0;
            for (int j = 2; j <= sqrt(c); j++)
            {
                if (c % j == 0)
                {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0)
            {
                count++;
            }
        }
        cout << count;
    }
    return 0;
}

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

Mike_python小

你的代码存在两个问题。

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

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

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

#include <iostream>#include <cmath>using namespace std;int main() {    int t, n;    cin >> t;    int a[t], b[t];    for (int i = 0; i < t; i++) {        cin >> a[i];        b[i] = 0;    }    for (int i = 0; i < t; i++) {        for (int c = 2; c <= a[i]; c++) {            int flag = 0;            for (int j = 2; j <= sqrt(c); j++) {                if (c % j == 0) {                    flag = 1;                    break;                }            }            if (flag == 0) {                b[i]++;            }        }    }    for (int i = 0; i < t; i++) {        cout << b[i] << endl;    }    return 0;}

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

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

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