Printing the n'th prime numbers

This is an online problem. The challenge is to print the kth prime number, for each k given in the input (1 ≤ k ≤ 15000). The first line of input indicates the number of inputs on the subsequent N lines.

Example input:

4
1
2
3
4

Example output:

2
3
5
7

(the 1st 2nd 3rd and 4th prime numbers).

#include 
#include 
#include 
#define MAX 100000000

void prime(int n)
{
    int i,j,temp,count=0;

    for(i=2;i<=MAX;i++)
    {
        temp=0;
        for(j=2;j<=sqrt(i);j++)
        {
            if(i%j==0)
            {
                temp=1;
                break;
            }
        }
        if(temp==0)
        {
            count++;
        }
        if(count==n)
        {
            printf("%d\n",i);
            break;
        }
    }
}

int main()
{
   int n,i;

   scanf("%d",&n);
   int arr[n];

   for(i=0;i<n;i++)
   {
       scanf("%d",&arr[i]);
   }
   for(i=0;i<n;i++)
   {
       prime(arr[i]);
   }

   return 0;
}

This code is working fine on codeblocks but is exceeding time limits on an online judge. I've tried manipulating this code in two more ways

• using pointer and malloc in the main function

• running the loop from j=1 to j=i/2 instead of upto sqrt(i)

(latter is more efficient due to fewer iterations of loop). Any suggestions?

You are trying to iterate over all numbers and check if each is prime which you do in O(n sqrt n) time. This might be feasible if you switch to a more efficient primality check, such as the Miller-Rabin primality test, as it is deterministic within certain limits depending on the probes.

A simpler way to do this is to generate primes until you are done. This can easily be done by the Sieve of Eratosthenes in roughly O(n log log n) time.

You can run the sieve once, get all the primes up to 175000 (15000th prime is 163841 according to a bit of googling) and then answer all the queries in constant time by dumping all the primes into an ArrayList (in order of course).

If those methods aren't fast enough, look into even faster sieving algorithms such as Sieve of Sundaram and Sieve of Atkin.

StackExchange Code Review Q#86774, answer score: 6