Find prime positioned prime number

This is a question from programming contest. This contest is already over.

Now, all the prime numbers are arranged sequentially in ascending order. i.e:- 2, 3, 5,7...and so on. Now, your task is to calculate those prime numbers which are present at a prime position. For example, 2 is present at position 1 which is not a prime number while 3 is present at position 2 which is a prime number, hence 3 is the first prime positioned number. Now, these primed positioned prime numbers are numbered is ascending order such that:

first prime positioned number is 3. So, it is given number 1.

second prime positioned number is 5. So, it is given number 2.

and so on. Now, we are given 2 numbers n and m which denotes the nth and mth prime positioned numbers. Now, your task is to calculate the multiplication of prime positioned number present at nth and mth position. Since the answer may be large, output the answer modulo 109 + 7.

INPUT

First line contains an integer t denoting the number of test cases. The next t lines contains two integers n and m separated by space, denoting the prime positioned numbers which are given numbers n and m.

OUTPUT

A single integer (one per line) for each test t, that is the answer to the question.

CONSTRAINTS

16

1<= n,m <=10000

My approach:

For each test case read 'n' and 'm'. Then calculate nthPrime for 'n' and 'm'.Then again calculate nthPrime for result each result and finally multiply both the answers. This is working for small input but for large inputs it is taking more time.

```
import java.util.Scanner;

public class Sum {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int t=scanner.nextInt();

while(t-- >0){
int n=scanner.nextInt();
int m=scanner.nextInt();
int first=nthPrime(nthPrime(n));
int second=nthPrime(nthPrime(m));

System.out.println(first*second);
}

}

private static int nthPrime(int n) {
// TODO Auto-generated method s

Knowing the time limit helps determine what kind of effort is needed to make the code fast enough:

• simple trial division

• trial division with wheeled striding through candidates and divisors

• trial division with memoised divisor primes and wheeled striding through candidates

• Sieve of Eratosthenes

• odds-only Sieve of Eratosthenes

• segmented odds-only Sieve of Eratosthenes

• segmented odds-only Sieve of Eratosthenes with presieving

Each complication makes the code significantly faster, but also more complex. So how fast is fast enough?

Generally speaking, the primes up to any given k should only be computed once total instead of twice for each query. Also, given the fact that the query count limit is much higher than the piddling small numbers of primes involved (10000) it makes sense to compute all of them in one go, which is much more efficient and much less complicated than writing some logic that can extend the current list of prime-indexed primes up to some number k when it is too short.

The high number on queries also makes it imperative to benchmark the code for parsing inputs and producing outputs, since that can easily dominate the total program runtime. SPOJ's INOUTEST - and the same or similar tasks at other sites - can be a good guide there.

I've had several such tasks where my submissions clocked times of several seconds or even TLE, even though the raw problem-solving part took only a few milliseconds to run. Writing a dedicated input parser and (batched) output converter cut runtime by two orders of magnitude or more.

Based on my experience recently solving problems of similar structure and magnitude (SPOJ's TDPRIMES and TDKPRIME) I would recommend using a segmented odds-only Sieve of Eratosthenes for building the list of prime-indexed primes in one go. That gives you the best performance for the least amount of complications. It would be possible to speed up your trial division by several orders of magnitude but then it would be more complex than the sieving solution, and the sieve would still blow it out of the water despite using simpler code.

I tried quite a few approaches and strategies, and perhaps my experiences can help you avoid going down some blind alleys.

Recommendation: use an odds-only sieve with bool array that is the same size as your CPU's L1 cache, e.g. 32 KiByte.

Using packed bits in a byte array would allow sieving eight times as much per cache-sized window, and extraction of primes from the sieve would be much more efficient. However, the overhead of indexing (sieve[j>>3] |= 1 << (j&7) instead of a simple sieve[j] = true) means that the sieving using byte[] took slightly longer overall in my tests than sieving plus extraction using bool[], even though the bool code had to sieve eight times as many windows. I was able to make byte[] 30% faster than bool[] but the effort required was essentially the same as that for a modulo 30 wheel, tripling the total size of the source code. Using the stock bitsets of C# (BitArray) and C++ (std::vector) was an unmitigated performance disaster; the whole program took several times as long to run just because of their mind-boggling inefficiency.

Recommendation: use functions that focus on a specific part of the job and that do whole batches at a time with maximum efficiency.

For example, I found it much faster to extract all primes from a sieved window and then pick out every hundredth from that, instead of integrating the 'take only every 100th prime' bit into the code that extracts primes from the sieve. The reason is focus and simplified looping/branching structures. Modern CPU don't like unpredictable branches at all and levy heavy taxes on them in the form of wait cycles. Better factoring also makes it easier to try different approaches for different sub tasks, for example via function pointers or delegates that can be switched at runtime. And it makes it easier to compose new, completely different solutions from the existing bits and pieces.

For example, instead of complicating - and thus slowing down - the sieve code by the logic for memoising the small handful of primes needed for sieving, I used a separate function for that purpose. Here is the pseudocode (of a hashish persuasion):

internal static List small_odd_primes_up_to (int n)
{
    Trace.Assert(3 > 1;     

    // the '- 1' comes from the number-to-bit conversion again and is not related to the sqrt
    int sqrt_n_bit = (int)(Math.Sqrt(n) - 1) >> 1;
    var sieve = new bool[max_bit + 1];

    for (int i = 3 >> 1; i > 1; j ()  {  3  };

    for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
        if (!sieve[i])
            result.Add((ushort)((i << 1) + 1));

    return result;
}

In your case it would have to deliver only the 1168 odd sieve primes, i.e. those not greater than sqrt(1366661) where 1366661 is the 104729th prime and the 10000th prime-indexed prime. This means that the optimisations it contains - odds

StackExchange Code Review Q#125018, answer score: 8