Sphere Online Judge, Problem 2: Prime Number Generator I am trying to solve this problem on Sphere Online Judge. I keep getting a timeout error. Any comments or suggestions are welcome and appreciated.

package info.danforbes.sphere;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.nio.charset.MalformedInputException;
import java.util.AbstractMap.SimpleEntry;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map.Entry;

public class PrimeNumberGenerator {
  private static BufferedReader inStream;
  private static BufferedWriter outStream;
  private static List&lt;Entry&lt;Integer, Integer&gt;&gt; pairs = new ArrayList&lt;Entry&lt;Integer, Integer&gt;&gt;();
  private static HashSet&lt;Integer&gt; primes = new HashSet&lt;Integer&gt;();

  private static void getPairs(int numCases) throws MalformedInputException {
    String line;
    int spaceNdx;
    int num1, num2;
    try {
      for (int pairNdx = 0; pairNdx &lt; numCases; ++pairNdx) {
        line = inStream.readLine();
        spaceNdx = line.indexOf(' ');
        num1 = Integer.parseInt(line.substring(0, spaceNdx));
        num2 = Integer.parseInt(line.substring(spaceNdx + 1));
        if (num1 &lt; 1) throw new MalformedInputException(num1);
        if (num1 &gt; num2) throw new MalformedInputException(num2 - num1);
        if (num2 &gt; 1000000000) throw new MalformedInputException(num2);
        if (num2 - num1 &gt; 100000) throw new MalformedInputException(num2 - num1);
        pairs.add(new SimpleEntry&lt;Integer, Integer&gt;(num1, num2));
      }
      inStream.close();
    } catch (IOException e) {
      System.out.println("IOException encounterd!");
      e.printStackTrace();
      System.exit(-1);
    }
  }

  private static boolean isPrime(int num) {
    boolean isPrime = true;
    if (num &lt; 2) isPrime = false;
    else if (num &gt; 3) {
      if (num % 2 == 0 || num % 3 == 0) isPrime = false;
      else if (!primes.contains(num)){
        int sqrRoot = (int)Math.sqrt(num);
        for (int factorNdx = 1; 6 * factorNdx - 1 &lt;= sqrRoot; ++factorNdx) {
          if (num % (6 * factorNdx + 1) == 0 || num % (6 * factorNdx - 1) == 0) {
            isPrime = false;
            break;
          }
        }
      }
    }

    if (isPrime) primes.add(num);
    return isPrime;
  }

  public static void main(String[] args) {
    if (args.length == 0) {
      inStream = new BufferedReader(new InputStreamReader(System.in));
      outStream = new BufferedWriter(new OutputStreamWriter(System.out));
    }

    StringBuilder resultBuilder = new StringBuilder();

    try {
      if (inStream == null &amp;&amp; outStream == null) {
        inStream = new BufferedReader(new FileReader(args[0]));
        outStream = new BufferedWriter(new FileWriter(args[1]));
      }

      int numCases = Integer.parseInt(inStream.readLine());
      if (numCases &gt; 10) throw new MalformedInputException(numCases);
      getPairs(numCases);
      int beg, end;
      for (Entry&lt;Integer, Integer&gt; anEntry : pairs) {
        beg = anEntry.getKey();
        end = anEntry.getValue();
        for (int rangeNdx = beg; rangeNdx &lt;= end; ++rangeNdx) {
          if (isPrime(rangeNdx)) resultBuilder.append(Integer.toString(rangeNdx) + "\n");
        }

        resultBuilder.append("\n");
      }

      resultBuilder.delete(resultBuilder.length() - 2, resultBuilder.length());
      outStream.write(resultBuilder.toString());
      outStream.close();
    } catch (IOException e) {
      System.out.println("IOException encountered!");
      e.printStackTrace();
      System.exit(-1);
    }
  }
}
I'll make general statements not addressing (or not limited to) performance.



Your overall design is not very Object-Oriented. Usage of static/global variables is discouraged for a reason, it is very hard to follow the flow the program. Consider rewriting it with proper classes/encapsulation.

You could extract reading into one function, which then returns the list of pairs which another function can work on. Some pseudo code:

main()
    List pairs
    if args provided
        pairs = pairsFromFile(args[0])
    else
        pairs = pairsFromStdIn()

    foreach pair in pairs
        processpair(pair)




Your usage of one-line ifs is partly confusing, consider to expand those to at least two lines for readability:

if(test)
    return true;




You're declaring and actively throwing exceptions which never get caught, that means that your application will exit with a thrown exception, that's a bad thing. Applications should handle exceptions at least in the main loop and exit gracefully.



Consider writing directly to the output-stream instead of buffering everything in a StringBuilder. While it might hurt performance if you're doing a lot of writing, it will remove some of the complexity.



System.out.println("IOException encounterd!");


Exceptions and errors should traditionally go to System.err.



You're using System.exit() at some places, it might be more desirable to let the main loop handle the application flow instead of "exiting" from any or some functions. I also now realize that you're using some sort of template to handle exceptions (write to out, print stacktrace, exit(-1)), please don't just slap an "error-handling-template" on it and be done with it. Handle exceptions in a context-sensitive way.



isPrime() does use a temporary variable isPrime when returning at the appropriate places would be more then enough.

private static boolean isPrime(int num) {
  if (num &lt; 2)
    return false;
  else if (num &gt; 3) {
    // Loop here
        if (num % (6 * factorNdx + 1) == 0 || num % (6 * factorNdx - 1) == 0) {
          return false;
        }
  }

  if (isPrime) primes.add(num);
  return true;
}