Segmented Sieve of Eratosthenes

The classical 'sieve of eratosthenes'(if you don't know this please read it first)
 generates prime no. starting from 1 upto a limit. However if you want to sieve prime numbers between two given numbers, segmented sieve is used. For example if you want prime numbers between say 125 and 150, you need not sieve primes upto 150 and then check how many of them are above 125. The approach is basically to create a bool array of size 25 (150-125) in this case. i-th index of your bool array will correspond to (125+i) number. Then mark non prime no. as follows start from (125/2)*2=124, now begin from 126 (124+2 because you need primes greater than 125 )and remove all no. at a distance of 2, ie 126,128,130...150. () This removes all even no. Then start from (125/3)*3=123,now begin from 126 and remove all elements at distance 3,ie 126,129,132,...150. This removes all multiples of 3. Proceed in similar fashion removing all multiples of prime upto sqrt(150).

To be more generalized, given two no. say m and n, prime no. between m and n can sieved by creating a bool array of size n-m. i th index of the array will correspond to (m+i) no. Sieve all primes by using primes up-to sqrt(n) by doing (m/prime)*prime following the fashion shown in example above.
(Credits: Ayur Jain for above explanation)

Implementation in Java:
public class SegmentedSieve {
public static void main(String[] args) {
    int s=125,e=150;
    int eSqrt = (int)Math.sqrt(e);
    boolean[] b = new boolean[eSqrt+1];
    Arrays.fill(b, true);
    b[0]=b[1]=false;
    for(int i=2;i<=eSqrt;i++){
        if(b[i]){
            for(int j=i*i;j<eSqrt;j+=i)b[j]=false;
        }
    }
    boolean[] segment = new boolean[e-s+1];
    Arrays.fill(segment, true);
    for(int i=2;i<=eSqrt;i++){
        if(b[i]){
            for(int j=((s/i)*i);j<=e;j+=i)if(j>=s)segment[j-s]=false;
        }
    }
   
    for(int i=0;i<segment.length;i++){
        System.out.println((s+i)+":"+segment[i]);
    }
}
}