title: Sieve of Eratosthenes problem: handling really big numbers
body: <p>I'm solving Sphere's Online Judge <a href="https://www.spoj.pl/problems/PRIME1/" rel="nofollow noreferrer">Prime Generator</a> using the Sieve of Eratosthenes. </p>
  
  <p>My code works for the test case provided. But.. as the problem clearly states:</p>
  
  <blockquote>
    <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 (<strong>1 &lt;= m &lt;= n &lt;=
    1000000000, n-m&lt;=100000)</strong> separated by
    a space.</p>
  </blockquote>
  
  <p>I know that the method <code>Integer.parseInt()</code> throws an Exception when handling really big numbers and the online judge was indicating that an Exception was being thrown, so I changed every case of <code>parseInt</code> to <code>parseLong</code> in my code. </p>
  
  <p>Well, the thing is running fine on Netbeans 6.5 with small values for m and n.</p>
  
  <pre><code>package sphere;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  
  public class Main{
  
  public static void runEratosthenesSieve(long lowerBound, long upperBound) {
  
        long upperBoundSquareRoot = (long) Math.sqrt(upperBound);
  
        boolean[] isComposite = new boolean[(int)upperBound + 1];
  
        for (int m = 2 /*int m = lowerBound*/; m &lt;= upperBoundSquareRoot; m++) {
  
              if (!isComposite[m]) {
  
                  if (m&gt;=lowerBound) {System.out.println(m);}
  
                    for (int k = m * m; k &lt;= upperBound; k += m)
  
                          isComposite[k] = true;
  
              }
  
        }
  
        for (int m = (int)upperBoundSquareRoot; m &lt;= upperBound; m++)
  
              if (!isComposite[m])
  
                   if (m&gt;=lowerBound){ System.out.println(m);}
  
  }
  
  public static void main(String args[]) throws java.lang.Exception{
  
         BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
  
  
         String l = r.readLine();
  
         int testCases = Integer.parseInt(l); 
  
         for (int i =0; i&lt;testCases; i++){
         String s =r.readLine();
  
         String []splitted=s.split(" ");
  
  
         long lowerBound = Long.parseLong (splitted[0]);
         long upperBound = Long.parseLong(splitted[1]);
  
         runEratosthenesSieve (lowerBound,upperBound);
  
         System.out.println("");
         }
  }
  
  }
  </code></pre>
  
  <p>Input+Output:</p>
  
  <pre><code>run:
  2
  1 10
  2
  3
  3
  5
  7
  
  3 5
  3
  5
  
  BUILD SUCCESSFUL (total time: 11 seconds)
  </code></pre>
  
  <p>But JCreator LE is saying this:</p>
  
  <pre><code>2
  1 10
  Exception in thread "main" java.lang.NumberFormatException: For input string: ""
      at java.lang.NumberFormatException.forInputString(NumberFormatException.java:48)
      at java.lang.Long.parseLong(Long.java:424)
      at java.lang.Long.parseLong(Long.java:461)
      at sphere.Main.main(Main.java:51)
  
  Process completed.
  </code></pre>
  
  <p>Here I don't have an integer overflow, but why would jcreator complain? </p>
  
  <p>Considering the borderline testcase, the program implodes on Netbeans too:</p>
  
  <pre><code>run:
  2
  999900000 1000000000 
  Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
          at sphere.Main.runEratosthenesSieve(Main.java:13)
          at sphere.Main.main(Main.java:55)
  Java Result: 1
  </code></pre>
  
  <p>How can I deal with those huge-ish integers of the problem statement? </p>
  
  <p><strong>Edit:</strong> By suggestion I have changed the boolean array for a BitSet, but I'm still getting an <code>OutOFMemoryError</code>:</p>
  
  <pre><code>package sphere;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.BitSet;
  
  public class Main{
  
  public static void runEratosthenesSieve(long lowerBound, long upperBound) {
  
        long upperBoundSquareRoot = (long) Math.sqrt(upperBound);
  
        //boolean[] isComposite = new boolean[(int)upperBound + 1];
  
        BitSet isComposite = new BitSet((int)upperBound+1);
  
        for (int m = 2 /*int m = lowerBound*/; m &lt;= upperBoundSquareRoot; m++) {
  
              if (!isComposite.get(m)) {
  
                  if (m&gt;=lowerBound) {System.out.println(m);}
  
                    for (int k = m * m; k &lt;= upperBound; k += m)
  
                          isComposite.set(m);
  
              }
  
        }
  
        for (int m = (int)upperBoundSquareRoot; m &lt;= upperBound; m++)
  
              if (!isComposite.get(m))
  
                   if (m&gt;=lowerBound){ System.out.println(m);}
  
  }
  
  public static void main(String args[]) throws java.lang.Exception{
  
         BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
  
  
         String l = r.readLine();
  
         int testCases = Integer.parseInt(l); 
  
         for (int i =0; i&lt;testCases; i++){
         String s =r.readLine();
  
         String []splitted=s.split(" ");
  
  
         long lowerBound = Long.parseLong (splitted[0]);
         long upperBound = Long.parseLong(splitted[1]);
  
         runEratosthenesSieve (lowerBound,upperBound);
  
         System.out.println("");
         }
  }
  
  }
  </code></pre>
  
  <p>Input-Output:</p>
  
  <pre><code>run:
  1
  999900000 1000000000
  Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
          at java.util.BitSet.initWords(BitSet.java:144)
          at java.util.BitSet.&lt;init&gt;(BitSet.java:139)
          at sphere.Main.runEratosthenesSieve(Main.java:16)
          at sphere.Main.main(Main.java:58)
  Java Result: 1
  BUILD SUCCESSFUL (total time: 14 seconds)
  </code></pre>