6
$\begingroup$

enter image description here

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.

$\endgroup$
4
  • $\begingroup$ Is it really a formula, or more like a program / procedure? $\endgroup$
    – coffeemath
    Commented Jun 28, 2014 at 9:11
  • 1
    $\begingroup$ 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 $\endgroup$
    – Lakshman
    Commented Jun 28, 2014 at 9:55
  • $\begingroup$ 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] $\endgroup$
    – coffeemath
    Commented Jun 28, 2014 at 11:34
  • $\begingroup$ 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. $\endgroup$
    – Lakshman
    Commented Jun 28, 2014 at 12:59

1 Answer 1

0
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .