[Math] Prime Triangle:: How to find the position(row and column) of prime number in a triangular arrangement

Question

I was working on problem which asks the position of a prime number in a triangular arrangement.

If we arrange the all prime up to $10^8$ as shown in image we can find the row and column number of a given prime. I have a correct formula for finding the row and column of prime which runs in $O (\log n)$. I just want to know is there any $O(1)$ formula to compute the row and column.

Answer 1

This question may require the precomputation of the positions of each prime number in the triangle.

Here is a way to precompute the positions

void find_position()
{
    vector<pair<int, int>> res(MAX);
    long row=1, col=1;
    res[2]=make_pair(row, col);
    col+=1;
    for(long i=3;i<MAX;i+=2)
    {
        if(row<col)
        {
            row+=1;
            col=1;
        }
        if(prime[i])
        {
            res[i]=make_pair(row,col);
            col+=1;
        }
    }
}

prime is a boolean vector that tells if the ith value is prime or not.

MAX is defined as 10^8.

After precomputing the positions, for each input n we can simply check if it is prime then print the nth value from res.

The time complexity of precomputing the positions is O(n/2) and for each query is O(1).