Reducing time limit for prime number program I have to create a program in which t sets of m and n will be given by the user. For each set, we have to generate all prime numbers between m and n.  This code is successfully executed with the correct output, but I have to reduce the time limit for a large data range.

#include&lt;math.h&gt;
#include&lt;stdio.h&gt;
int isPrime(int k); 
int j;
int isPrime(int k) 
 {
  for(j=2; j&lt;=(int)sqrt(k); j++) 
    {
      if(k%j==0)
      return 0;
    }
  return 1;
}

int main()
{
   int u,i,t,m,n,k;        
   scanf("%d", &amp;t);
   while(t--)
       {       
         scanf("%d %d", &amp;m, &amp;n);

         for(i=m;i&lt;=n;i++)
             {
                  u = isPrime(i);
                  if (u == 1)
                  printf("%d\n", i);
             }
       }
   return 0;
}
For this SPOJ problem with (1 &lt;= m &lt;= n &lt;= 1000000000, n-m&lt;=100000) limits you will have to use an offset sieve of Eratosthenes. 

Since n &lt;= 10^9, to sieve any range under n it is sufficient to have just the primes below its square root, 31622, pre-calculated. There are only 3401 such primes, the biggest being 31607. 

So, A. pre-calculate the 3401 primes below 31622.

Since n-m&lt;=100000, you can B. have one array of 100000 booleans preallocated, and sieve it by those primes, as in sieve of Eratosthenes, for each pair m,n.

As an easy optimization, use that sieve segment to represent just odds, without evens: an entry at position i will represent odd(m) + 2*i where odd(m) is the lowest odd number not below m in value. Sieve this segment by odd primes only. No even number above 2 is ever a prime:

for i = 3, 5 ... √n in primes:
   for j = i^2, i^2+2*i, i^2+4*i ...   inside the segment  m ... n:
      A{j} := false