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

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.

• Is it really a formula, or more like a program / procedure? Commented Jun 28, 2014 at 9:11
• Actually we first we need to find all primes till 10^8 and store them in an array and there are m quires each query followed by some prime or composite number if number is prime print the position(row and column) of that prime number in Prime Triangle. problem link spoj.com/problems/PTRI2 and My timing spoj.com/status/PTRI2,luckymastermin Commented Jun 28, 2014 at 9:55
• When you say O(log n) what is n? The number like 10^8 which is the upper bound for the primes, or maybe it's the n of "n-th prime"... The choice here makes a difference when expressing how fast the procedure is. [I couldn't see how it could be O(1), i.e. bounded, since the number of rows is growing] Commented Jun 28, 2014 at 11:34
• 10^8 is upper bound for primes. Here is some points about My algorithm. I am pre-computing all prime till 10^8 using segmented sieve in O(n log log n) (here n<=10^8) time and then using Binary search I am finding the index of the given prime once I have the index of the prime number I can find its row and column position using that formula and formula is also O(log p) where p is prime number whose position we have to find. Commented Jun 28, 2014 at 12:59

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

• Thanks for your response, I managed to solve this problem. Commented Jun 1, 2020 at 4:56
• @Lakshman Can you please share your approach ?! I am precomputing primes using sieve method. But that alone is giving TLE ! Commented Aug 12, 2022 at 19:00