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:41234Example output:2357(the 1st 2nd 3rd and 4th prime numbers).#include <stdio.h>#include <stdlib.h>#include <math.h>#define MAX 100000000void 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?
Printing the n'th prime numbers
c;programming challenge;primes;time limit exceeded
Things that can be improved in the current algorithmBefore I start talking about other ways to find the primes, let's take a look at some of the things that could be improved in the current program.I don't think temp is a very good name.  I think you should change it to isPrime and then reverse the sense of it.You only need to check count==n if the number was prime, not in all cases.The break that you use when count==n actually causes the function to return.  It would be more clear to just say return instead of break.Instead of j<sqrt(i) as your loop condition, it would be better to just call sqrt(i) once before the loop instead of calling sqrt() once per loop.  A smart compiler will optimize this for you, but you can't always depend on your compiler being that smart.Instead of iterating through all integers, you can only iterate through all odd integers.  This goes for both loops.  The only even prime is 2 and you can check for that as a special case.So after all the adjustments above, your code would look like this:void prime(int n){    int i,j,count=0;    if (n == 1) {        printf(2\n);        return;    }    for(i=3;i<=MAX;i+=2)    {        int isPrime=1;        int jMax = sqrt(i);        for(j=3;j<=jMax;j+=2)        {            if(i%j==0)            {                isPrime=0;                break;            }        }        if(isPrime)        {            if(++count==n)            {                printf(%d\n,i);                return;            }        }    }}This code runs 2x faster than the original function.  But that's still not fast enough.Wasting computationThe way you are currently going about the problem is that you find each prime independently of the next.  So if you are asked to find the 150000th prime followed by the 149999th prime, you will spend a whole lot of time finding the 150000th prime and then throw away all your work and spend a whole lot of time finding the 149999th prime, even though you already found that prime the first time around!You could do a lot better by:Figuring out the biggest prime that you are asked for.Find all the primes up to that prime in one call to prime().Now that you have all the primes, print out the ones you were asked to find one by one.This reduces the problem by a factor of N, where N is the number of primes you were asked to find.  Let's see what this new program would look like:#include <stdio.h>#include <stdlib.h>#include <math.h>#define MAX 100000000void prime(int n, int *primes){    int i,j,count=0;    primes[count++] = 2;    if (count == n)        return;    for(i=3;i<=MAX;i+=2)    {        int isPrime=1;        int jMax = sqrt(i);        for(j=3;j<=jMax;j+=2)        {            if(i%j==0)            {                isPrime=0;                break;            }        }        if(isPrime)        {            primes[count++] = i;            if(count==n)                return;        }    }}int main(){   int n,i;   scanf(%d,&n);   int arr[n];   int maxPrime = 0;   for(i=0;i<n;i++)   {       scanf(%d,&arr[i]);       if (arr[i] > maxPrime)           maxPrime = arr[i];   }   int primes[maxPrime];   prime(maxPrime, primes);   for (i=0;i<n;i++)   {       printf(%d\n, primes[arr[i]-1]);   }   return 0;}Other waysOf course there are other ways to do this even faster.  For example, you can use the Sieve of Eratosthenes method.  But for the purposes of your online problem, I'm sure that the key factor was to use a one pass solution instead of an N pass solution.  That was the stumbling block in your current solution.