由于Hackerrank中的超时而终止（在cpp中使用malloc）

Question

所以我是一个非常新的程序员，我刚刚开始在Hackerrank上提问。我尝试了一个问题，它可以在离线ide上进行编译和工作。但是在hackerrank上显示错误。迅速回答将对我有帮助。

<< img src =“ https://image.soinside.com/eyJ1cmwiOiAiaHR0cHM6Ly9pLnN0YWNrLmltZ3VyLmNvbS9YQ2duZC5wbmcifQ==” alt =“在此处输入图像描述”>

这是质数螺旋的虚拟表示（出于理解目的）

现在有问题如上图所示，素数以螺旋形式从原点（0，0）开始并移动。右列和底行中显示的数字分别是列号和行号（即y和x坐标）

目标是找到给定素数的位置（x和y坐标）。

ERROR当我在hackerrank中运行代码时，3个测试用例中有2个可用。但是对于一个测试用例，它显示由于超时而终止了错误。我写的代码如下：

    #include<iostream>
using namespace std;
int prime(int a)
{
    int count, h=0;
    for (int i = 2; i <= 12000000; i++)
    {
        count = 0;
        for (int j = 2; j <= i; j++)
        {
            if(i%j==0)
            {
                count++;
            }
        }
        if (count == 1)
        {
            h = h + 1;
        }
        if (a == i)
        {
            break;
        }
    }
    return h;

}
void spiral(int h)
{
    int stepnum=1, totalsteps = 2;
    int x_coordinate = 0, y_coordinate = 0;
    int operatn = 1;
    for(int i=2;i<=h;i++)
    {
        if (stepnum <= (totalsteps/2))
        {
            x_coordinate = x_coordinate + operatn;
        }
        else
        {
            if (stepnum <= totalsteps)
            {
                y_coordinate = y_coordinate + operatn;
            }
        }
        if (stepnum == totalsteps)
        {
            stepnum = 0;

            operatn = -1 * operatn;

            totalsteps = totalsteps + 2;


        }
        stepnum++;

        }

    cout << "x coordinate = "<<x_coordinate<< " y coordinate = "<<y_coordinate<<endl;

}

int main()
{
    int t;
    int* p;
    cout<<"Enter the number of cases :"<< endl;
    cin >> t;
    int test;
    p=(int*)malloc(t*4);
    for (int i = 0; i < t; i++)
    {
        cin >> *(p+i);
    }
    for (int i = 0; i < t; i++)
    {
        test = prime(*(p + i));
        spiral(test);

    }
}

Answer 1

您的问题是此循环：

for (int i = 2; i <= 12000000; i++)
...
    for (int j = 2; j <= i; j++)
    ...

您最终将按照内部循环的n ^ 2次迭代的顺序进行操作，其中n = 12000000，因此内部循环的144 * 10 ^ 12次迭代。

假设每次迭代都需要1纳秒（实际上会更长），所以完成程序需要144 * 10 ^ 12/10 ^ 9 = 144000秒，或〜1.7天，除非您中断[ C0]。

因此，如果您的测试用例碰巧以较大的if (a == i)调用prime，则可能会超过分配的时间预算。