Sieve of Eratosthenes optimization I am making a program to find primes between the given range of numbers. Unfortunately, the algorithm I created is too slow. Do you have any ideas of how to optimize the code? 

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args)throws IOException {

        Scanner s = new Scanner(System.in);
        int numberOfTests;
        int l, n;
        numberOfTests = s.nextInt();

        for (int q = 0; q &lt; numberOfTests; q++) {
            l = s.nextInt();
            n = s.nextInt();
            if (l==1)l++;
            BitSet primeBitSet = new BitSet((int) (Math.sqrt(n) + 1));
            ArrayList &lt;Integer&gt; primeTable = new ArrayList &lt;Integer&gt;((int) Math.sqrt(n));
            if (l &lt; 1 || n &lt; 1 || l &gt; n || n &gt; 1000000000) {
                System.exit(0);
            }

            //classic sieve from 1 to sqrt(n)
            for (int j = 2; j * j &lt;= n; j++) {
                if (primeBitSet.get(j - 1) == true) {
                    continue;
                } else {

                    primeTable.add(j);
                    for (int k = 2 * j; k &lt;= n; k += j) {
                        primeBitSet.set(k - 1);
                    }
                }
            }



            //sieve in the expected range using primes generated by the classic sieve
            BitSet primesInRangeBitSet = new BitSet(n - l + 1);
            int pomoc;
            for (int i = 0; i &lt; primeTable.size(); ++i) {

                pomoc = l / ((int) primeTable.get(i));
                pomoc = pomoc * ((int) primeTable.get(i));
                for (int j = pomoc; j &lt;= n; j = j + (int) primeTable.get(i)) {

                    if (j &lt; l || primesInRangeBitSet.get(j - l) == true ) {
                        continue;
                    } else {
                        primesInRangeBitSet.set(j - l);
                    }
                }

            }

            //outputting the primes
            for (int k = 0; k &lt; primeTable.size(); k++){
                if((int)primeTable.get(k)&gt;= l &amp;&amp;(int) primeTable.get(k) &lt;= n)
                    System.out.println(primeTable.get(k));
            }
            for (int k = 0; k &lt; primesInRangeBitSet.size(); k++) {
                if (primesInRangeBitSet.get(k) == false &amp;&amp; k &lt;= n - l ) {
                    System.out.println((k + l));
                }
            }
            System.out.println("");
        }
    }
}
Variable scope

In order to make things easier to read/write, it is prefered to declare local variables as late as possible and in the smallest possible scope.

In your case, this holds for :

int numberOfTests = s.nextInt();




int l = s.nextInt();




int n = s.nextInt();




int pomoc = l / ((int) primeTable.get(i));


Also, BitSet primeBitSet can be declared just before the loop using it.

Continue

The way you use continue make things complicated for no obvious reasons.

            if (primeBitSet.get(j - 1) == true) {
                continue;
            } else {
                primeTable.add(j);
                for (int k = 2 * j; k &lt;= n; k += j) {
                    primeBitSet.set(k - 1);
                }
            }


can be written :

            if (!primeBitSet.get(j - 1)) {
                primeTable.add(j);
                for (int k = 2 * j; k &lt;= n; k += j) {
                    primeBitSet.set(k - 1);
                }
            }


New lines

The way you use new lines does not seem to make much sense. You should try to separate things into different "paragraphs".

After taking into accounts these comments about style, here's what the code would be like :

public class Main {

    public static void main(String[] args)throws IOException {
        Scanner s = new Scanner(System.in);
        int numberOfTests = s.nextInt();

        for (int q = 0; q &lt; numberOfTests; q++) {
            int l = s.nextInt();
            int n = s.nextInt();
            if (l==1)l++;
            ArrayList &lt;Integer&gt; primeTable = new ArrayList &lt;Integer&gt;((int) Math.sqrt(n));
            if (l &lt; 1 || n &lt; 1 || l &gt; n || n &gt; 1000000000) {
                System.exit(0);
            }

            //classic sieve from 1 to sqrt(n)
            BitSet primeBitSet = new BitSet((int) (Math.sqrt(n) + 1));
            for (int j = 2; j * j &lt;= n; j++) {
                if (!primeBitSet.get(j - 1)) {
                    primeTable.add(j);
                    for (int k = 2 * j; k &lt;= n; k += j) {
                        primeBitSet.set(k - 1);
                    }
                }
            }

            //sieve in the expected range using primes generated by the classic sieve
            BitSet primesInRangeBitSet = new BitSet(n - l + 1);
            for (int i = 0; i &lt; primeTable.size(); ++i) {
                int pomoc = (l / ((int) primeTable.get(i))) * ((int) primeTable.get(i));
                for (int j = pomoc; j &lt;= n; j = j + (int) primeTable.get(i)) {
                    if (j &gt;= l &amp;&amp; !primesInRangeBitSet.get(j - l)) {
                        primesInRangeBitSet.set(j - l);
                    }
                }
            }

            //outputting the primes
            for (int k = 0; k &lt; primeTable.size(); k++){
                if((int)primeTable.get(k)&gt;= l &amp;&amp;(int) primeTable.get(k) &lt;= n)
                    System.out.println(primeTable.get(k));
            }
            for (int k = 0; k &lt; primesInRangeBitSet.size(); k++) {
                if (primesInRangeBitSet.get(k) == false &amp;&amp; k &lt;= n - l ) {
                    System.out.println((k + l));
                }
            }
            System.out.println("");
        }
    }
}


Algorithm

Now, this being said, there is a much bigger issue here. If tou want to implement Sieve of Eratosthene properly, everything you need is just a BitSet of size 1.
If you really want to (but I don't really see the point), you can add primes numbers in a list as you detect them. If you just need to print them, you can print them as you detect them. In any case, I guess that from a performance point of view, it is not such a big deal to reiterate over the whole BitSet looking from prime numbers.