HackersEarth - Reverse primes

Question

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<Long> reversedCheckedPrime = new LinkedHashSet<Long>();
        int isPrimeLength = isPrime.length;
        for (int i = 0; i < isPrimeLength; i++) {
            if (isPrime[i]) {
                long prime = 2 * i + 3;
                long reverse = reversePrime(prime);
                if ((!(prime == reverse))
                        && (!reversedCheckedPrime.contains(reverse))
                        && (reversedCheckedPrime.size() <= 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 < root; i++) {
            if (isPrime[i]) {
                for (int j = 2 * i * (i + 3) + 3, p = 2 * i + 3; j < 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 < isPrimeLength; i++) {
            if (isPrime[i]) {
                long prime = 2 * i + 3;
                long revrse = reversePrime(prime);
                if ((!(prime == revrse))
                        && (!reversedCheckedPrime.contains(revrse))
                        && (reversedCheckedPrime.size() <= MAXLISTSIZE)) {
                    reversedCheckedPrime.add(prime);
                    outputResult.append(prime);
                    outputResult.append("\n");
                }
                if (reversedCheckedPrime.size() == MAXLISTSIZE) {
                    break;
                }
            }
        }

        System.out.println(outputResult);
    }

Question link for submission

Answer 1

Buggy

The output of your code contains many incorrect values. Looking at the first 10 numbers:

13
17
19
23
29
37
41
43
47
53

The reverse of 23, 29, 41, 43, 47, 53 are not primes.

Making it faster

With a small observation, you can make reversePrime much faster: if the first digit is 2, 4, 5, 6, 8, the reverse cannot be a prime, and you can stop computing the reverse immediately.

Another thing you can do, in addition to what @maaartinus suggested, is to not go all the way until \$10^6\$ primes. The problem description doesn't say you have to find all the primes, it just says to not print more than that.

Other bad practices

This expression is unnecessarily complicated:

if ((!(prime == reverse))
        && (!reversedCheckedPrime.contains(reverse))
        && (reversedCheckedPrime.size() <= MAXLISTSIZE)) {

Instead of !(prime == reverse), it's more intuitive to write prime != reverse.

There are so many unnecessary parentheses here that they are just noise and hurt readability.

The way @maaartinus rewrote it is the best of course.

---

The name of the reversePrime function, and the fact that it takes a parameter named prime suggests that it works specifically with primes, but actually it would work with any integer. It would be better to rename it accordingly to avoid confusion.

Another thing, it's not a good practice to modify parameter variables. It's better to copy them to a local variable and use that. So I would rewrite the function this way:

private static long reverse(long num) {
    long result = 0;
    long work = num;
    while (work != 0) {
        long remainder = work % BASE;
        work /= BASE;
        result = result * BASE + remainder;
    }
    return result;
}

Answer 2

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))
                    && (!reversedCheckedPrime.contains(revrse))
                    && (reversedCheckedPrime.size() <= MAXLISTSIZE)) {
                reversedCheckedPrime.add(prime);
            }

use

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

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

 reversedCheckedPrime.size() <= MAXLISTSIZE

was both wrong (should be <) 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.

Answer 3

Quick suggestions

1. As others have pointed out, the algorithm is incorrect because it doesn't check if the reverse is prime or not.
2. Instead of using a linked hash map, you can simply check if (prime < reverse) to make sure you don't get any duplicates.

Here is the main function after fixing it up:

public static void main(String args[]) {
    StringBuilder outputResult = new StringBuilder();
    int isPrimeLength = isPrime.length;
    int count = 0;
    for (int i = 0; i < isPrimeLength; i++) {
        if (isPrime[i]) {
            int prime    = 2 * i + 3;
            int reverse  = reversePrime(prime);
            if ((reverse & 1) == 0)
                continue;

            if (prime < reverse && isPrime[(reverse-3) >> 1]) {
                outputResult.append(prime);
                outputResult.append("\n");
                if (++count == MAXLISTSIZE) {
                    break;
                }
            }
        }
    }

    System.out.print(outputResult);
}

After making these changes and setting MAX to 100000000, I was able to generate 308618 "reverse primes" in 0.55 seconds.