Reducing time limit for prime number program

Question

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<math.h>
#include<stdio.h>
int isPrime(int k); 
int j;
int isPrime(int k) 
 {
  for(j=2; j<=(int)sqrt(k); j++) 
    {
      if(k%j==0)
      return 0;
    }
  return 1;
}

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

         for(i=m;i<=n;i++)
             {
                  u = isPrime(i);
                  if (u == 1)
                  printf("%d\n", i);
             }
       }
   return 0;
}    

Answer 1

For this SPOJ problem with (1 <= m <= n <= 1000000000, n-m<=100000) limits you will have to use an offset sieve of Eratosthenes.

Since n <= 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<=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

Answer 2

The main problem is: the algorithm contains a lot of divisions and a lot of function calls. A division can be very time consuming.

As Harish Ved said, the key is the sieve of Eratosthenes. It is one of the simplest and fastest way do determine if a number is prime. With that method, the problem can be solved by zero division and function call.

You should implement the sieve in the main function. You can find a lot of optimized examples on the internet. When You are done with that, You'll have an array, which contains the result of every IsPrime() method you can call. From that point, you only have to check an element of the array to know of a number is prime.

Here You can find a sample sieve (this can be optimized, but probably this will be able to solve the problem in the given time limit too).

You need a maximum value (MAXVAL), the primes smaller than that will be computed.

char *primes = (char*)malloc(MAXVAL*sizeof(char));
primes[0]=primes[1]=0;
for(i=2;i<MAXVAL;i++)
  primes[i]=1;    //allocating memory and filling with 1

for (i=2;i<MAXVAL;i++)
{
if(primes[i])
for(j=i*2;j<MAXVAL;j+=i)
 primes[j]=0;
} //setting the multiples of prime numbers to 0

This little algorithm will generate an array in wich the values at the primeth indexes will be 1, and other values will be 0. So after this, instead of calling Your IsPrime function with a lot of divisions, the prime check of n will look like

if(primes[n])

You can find a little working demonstration HERE