Reducing time limit for prime number program
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