c - How can I reduce the runtime? -

here link problem i'm trying solve: http://acm.timus.ru/problem.aspx?space=1&num=1086

here approach:

#include <stdio.h> #include <math.h>  int main() {     int n, i, m, p;      scanf("%d", &n);      for(i = 0; < n; i++)     {         scanf("%d", &m);          p = find_prime(m);         printf("%d\n", p);     }      return 0; }  int find_prime(int a) {     int i, p = 1, t, prime[15000], j;     prime[0] = 2;      for(i = 0; < a; )     {         if(p == 2)         {             p++;         }else         {             p = p + 1;         }         t = 0;         for(j = 0; prime[j] <= sqrt(p); j++)         {             if(p%prime[j] == 0 && p != 2)             {                 t = 1;                 break;             }         }         if(t != 1)         {             i++;             prime[i] = p;         }     }      return p; } 

i know algorithm fine , produces correct answer. "time limit exceeded". can't runtime download 2 seconds. it's equal 2.031 seconds. have tried few other approaches, example, iterated through numbers until found mth prime number, tried skipping integers greater 2 still 2.031 seconds.

what should do?

your buffer prime numbers doesn't need local variable that's recalculated every time.

you can try memoize storing buffer in global scope , using global counter keep track of how many primes have calculated until , number maximum number requested.

if next number that's requested smaller previous maximum, should fall corresponding pre-calculated number. if next number larger previous maximum, make new maximum - , try start calculating last left off.