Prime generator for SPOJ
The essence of the algorithm used by a sieve is removing the factors of the number. eg. first we remove the factors of 2 ie. 4,6, 8,10... , and then factors of 3 ie. 9 12, 15... so on and so forth.

But applying the same logic for bigger constraints would result in TLE. Thus segment sieve comes into picture.

The segment sieve also applies the same logic BUT on the segment. Thus, Segment Sieve works only if the segment length is within manageable constraints.

Consider a segment given by [m,n]. We remove all the factors which are greater than m but less than n. To check whether a number between m and n is a factor, we use a boolean array(is_factor)...whereis_factor[i] denotes whether the number which at a offset of i from lower bound of the segment(m). Now the factors are eliminated by considered all the numbers which are less than the sqrt(n).

Let's consider an example to illustrate my point.

Suppose m=1000 and n=1100 So we will remove all the factors of x( where x ranges from 2 to sqrt(1000)). 

Therefore, When x=2---> 1000,1002,1004,....1100 get crossed..(corresponding is_factor gets marked). 

When x=3 --> 1002,1005,1008,....1098 get crossed.. And the process continues.

So the ones which  remain unmarked are the primes in the interval [m,n].
This link illustrates a C++ program for solving the problem Prime 1 SPOJ
. Hope this helps mate :)