HackersEarth - Reverse primes Generate as many distinct primes P such that reverse (P) is also prime
  and is not equal to P.
  
  Output: Print per line one integer( ≤ 10^15 ). Don't print more than
  10^6 integers in all.
  
  Scoring: Let N = correct outputs. M = incorrect outputs. Your score
  will be max(0,N-M).
  
  Note: Only one of P and reverse(P) will be counted as correct. If both
  are in the file, one will be counted as incorrect.
  
  Sample Output: 107 13 31 17 2
  
  Explanation
  
  Score will be 1. Since 13,107,17 are correct. 31 is incorrect because
  13 is already there. 2 is incorrect.
  
  Time Limit: 2 sec(s) for each input file. Memory Limit: 256 MB Source
  Limit: 25 KB


public class ReversePrime {

    final static int MAX = 1000000;
    final static int MAXLISTSIZE = 1000000;
    final static int BASE = 10;

    final static boolean[] isPrime = generatePrime();

    public static void main(String args[]) {
        Set&lt;Long&gt; reversedCheckedPrime = new LinkedHashSet&lt;Long&gt;();
        int isPrimeLength = isPrime.length;
        for (int i = 0; i &lt; isPrimeLength; i++) {
            if (isPrime[i]) {
                long prime = 2 * i + 3;
                long reverse = reversePrime(prime);
                if ((!(prime == reverse))
                        &amp;&amp; (!reversedCheckedPrime.contains(reverse))
                        &amp;&amp; (reversedCheckedPrime.size() &lt;= MAXLISTSIZE)) {
                    reversedCheckedPrime.add(prime);
                }
                if (reversedCheckedPrime.size() == MAXLISTSIZE) {
                    break;
                }
            }
        }

        for (Long prime : reversedCheckedPrime) {
            System.out.println(prime);
        }

    }

    private static long reversePrime(long prime) {
        long result = 0;
        long rem;
        while (prime != 0) {
            rem = prime % BASE;
            prime = prime / BASE;
            result = result * BASE + rem;
        }
        return result;
    }

    private static boolean[] generatePrime() {
        int root = (int) Math.sqrt(MAX) + 1;
        root = root / 2 - 1;
        int limit = (int) ((MAX - 1) / 2);
        boolean[] isPrime = new boolean[limit];
        Arrays.fill(isPrime, true);
        for (int i = 0; i &lt; root; i++) {
            if (isPrime[i]) {
                for (int j = 2 * i * (i + 3) + 3, p = 2 * i + 3; j &lt; limit; j = j
                        + p) {
                    isPrime[j] = false;
                }
            }

        }
        return isPrime;
    }
}


While the code is working the real concern is the time limit. I'm not able to get it below 2 seconds. How could I further improve the runtime?

One way I reduced it further by avoiding the println() call in the for loop by doing this:

StringBuilder outputResult = new StringBuilder();
        for (int i = 0; i &lt; isPrimeLength; i++) {
            if (isPrime[i]) {
                long prime = 2 * i + 3;
                long revrse = reversePrime(prime);
                if ((!(prime == revrse))
                        &amp;&amp; (!reversedCheckedPrime.contains(revrse))
                        &amp;&amp; (reversedCheckedPrime.size() &lt;= MAXLISTSIZE)) {
                    reversedCheckedPrime.add(prime);
                    outputResult.append(prime);
                    outputResult.append("\n");
                }
                if (reversedCheckedPrime.size() == MAXLISTSIZE) {
                    break;
                }
            }
        }

        System.out.println(outputResult);
    }


Question link for submission
Just a simple idea: From each pair, you generate both the smaller and the bigger prime. You're using a Set in order to assure that you don't output both. But this can be done much simpler:

Instead of

            long revrse = reversePrime(prime);
            if ((!(prime == revrse))
                    &amp;&amp; (!reversedCheckedPrime.contains(revrse))
                    &amp;&amp; (reversedCheckedPrime.size() &lt;= MAXLISTSIZE)) {
                reversedCheckedPrime.add(prime);
            }


use

            long revrse = reversePrime(prime);
            if (prime &lt; revrse) {
                reversedCheckedPrime.add(prime);
            }


You simply add the smaller one only (which also handles the case of -self-reversed numbers). The test

 reversedCheckedPrime.size() &lt;= MAXLISTSIZE


was both wrong (should be &lt;) and useless (as there's a break later).

Now you can replace the Set by a List and gain some speed. You can gain even more, if you use a long[] of length MAXLISTSIZE (which should be called MAX_LIST_SIZE) as you avoid autoboxing.