Prime generator for SPOJ I have written code to solve the prime generator problem. I am given an input which contains in the first line the number of test cases, and for each test case, I am given a range and I have to print the list of prime numbers in that range. However, it doesn't pass and says that time limit has exceeded. I tried optimizing the code as best as I could, but I couldn't find any further optimization.

import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.Set;


class Primes {

private static Set&lt;Long&gt; primes = new LinkedHashSet&lt;Long&gt;();
private static long biggestPrime = 0;

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int numberOfTC = scanner.nextInt();

    for (int i = 0; i &lt; numberOfTC; i++) {

        long a = scanner.nextInt();
        long b = scanner.nextInt();
        long startFrom = a;

        if (a &gt;= biggestPrime) {
            startFrom = biggestPrime;
        } 
        if (biggestPrime == 0) {
            startFrom = 2;
        }
        for (long j = startFrom; j &lt;= b; j++) {
            if (isPrime(j) &amp;&amp; j &gt;=a)  {
                System.out.println(j);
            }
        }
        System.out.println();
    }
    scanner.close();

}

private static boolean isPrime(long x) {
    if (x &lt; biggestPrime) {
        if (primes.contains(x)) {
            return true;
        }
        return false;
    }
    for (Long prime : primes)
    {
        if (prime*prime &gt; x ) {
            break;
        }
        if (x % prime == 0) {
            return false;
        }
    }
    if (biggestPrime &lt; x) {
        primes.add(x);
        biggestPrime = x;
    }
    return true;
}
}
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 :)