title: Program to find all primes in a very large given range of integers
body: <p>i came across this following question on a programming website :
  Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!</p>
  
  <p>Input</p>
  
  <p>The input begins with the number t of test cases in a single line (t&lt;=10). In each of the next t lines there are two numbers m and n (1 &lt;= m &lt;= n &lt;= 1000000000, n-m&lt;=100000) separated by a space.</p>
  
  <p>I came up with the following solution : </p>
  
  <pre><code>import java.util.*;
  
  public class PRIME1 {
      static int numCases;
      static int left, right;
      static boolean[] initSieve = new boolean[32000];
      static boolean[] answer;
  
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          numCases = sc.nextInt();
          initSieve[0] = true;
          initSieve[1] = true;
          Sieve();
          for (int j = 0; j &lt; numCases; j++) {
              String line = sc.next();
              String line2 = sc.next();
              left = Integer.parseInt(line);
              right = Integer.parseInt(line2);
              answer = new boolean[right - left + 1];
              getAnswer();
              for (int i = 0; i &lt; answer.length; i++) {
                  if (!answer[i]) {
                      int ans = i + left;
                      System.out.println(ans);
                  }
              }
              System.out.println();
          }
      }
  
      public static void Sieve() {
  
          for (int i = 2; i &lt; 32000; i++) {
              if (!initSieve[i]) {
                  for (int j = 2 * i; j &lt; 32000; j += i) {
                      initSieve[j] = true;
                  }
              }
              if (i * i &gt; 32000)
                  break;
          }
      }
  
      public static void getAnswer() {
          for (int i = 2; i &lt; 32000 &amp;&amp; i &lt;= right; i++) {
              if (!initSieve[i]) {
                  int num = i;
                  if (num * 2 &gt;= left) {
                      num *= 2;
                  } else {
                      num = (num * (left / num));
                      if (num &lt; left)
                          num += i;
                  }
                  for (int j = num; j &gt;= left &amp;&amp; j &lt;= right; j += i) {
                      answer[j - left] = true;
                  }
              }
          }
      }
  }
  </code></pre>
  
  <p>I have edited my solution after reading some of the suggestions. I am still getting a time limit exceeded kind of error. Any more suggestions as how to further optimize this ? Am calculating all the primes upto 32000 and then using these to find the primes between n to m.</p>
  
  <p>Thanks,
  Rohit</p>