Terminated due to timeout in Hackerrank (using malloc in cpp)

Question

so I am pretty new programmer and I have just started doing questions on Hackerrank. I tried a question and it compiles and work on offline ide. But shows error on hackerrank. A prompt answer would really help me.

This is the Virtual representation of the Spiral of prime numbers(For understanding purposes)

Now the problem The prime numbers are written in a spiral form starting from the origin (0, 0) and moving as shown in the diagram above. The numbers shown in the right column and the bottom row are the column numbers and row numbers respectively ( i.e. y and x coordinates)

The objective is to find the position (x and y coordinates) of a given prime number.

ERROR When I run the code in hackerrank 2 out of 3 test cases work. But for one test case it shows Error terminated due to timeout. The code I wrote is the following :

    #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

Your problem is this loop:

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

You will end up doing on the order of n^2 iterations of your inner loop, where n=12000000, so that's 144*10^12 iterations of your inner loop.

Let's assume every iteration takes 1 nanosecond (it will actually be a lot longer), so that's 144*10^12 / 10^9 = 144000 seconds, or ~1.7 days, for a call to prime to complete, unless you break on if (a == i).

So if your test case happens to call prime with a large a, exceeding the allotted time budget is likely.