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

• maaartinus: You should also link to your previous questions concerning this (IIRC there was something here or on SO).
• Ankur Anand: @maaartinus This space issue was on SO which you solved .. :) link stackoverflow.com/questions/30573423/…

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;
}

• Ankur Anand: About your observation that was pretty nice thing to point .. ! but many incorrect value like ??
• maaartinus: @AnkurAnand All of them? :D I can't see isPrime[revrse] anywhere (and fix the typo).
• Ankur Anand: @maaartinus All of them ? .. by isPrime[revrse] you are suggesting i should check if the the reversed number is also prime or not ? right .. yeah will fix that revrse :)
• Ankur Anand: @maaartinus got what you were saying with isPrime[revrse] .. thank you both of you to point out that .. then actually i've not even understood the questions properly on first go :(

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.

• Ankur Anand: like always that was pretty clean answer and observation .. Thank you so much :)

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.

• Ankur Anand: Thanks for the suggestion .. yeah i figured out that yesterday after their comment about buggy thing.. 308618 is my score too there yesterday .. Thank you for conforming me that this will the highest score ..:D my submission hackerearth.com/submission/1909283
• JS1: @AnkurAnand If you want to look at the ultimate solution, take a look at this submission, which used separate sieves on numbers starting with 1,3,7,9 because the other numbers can't possibly work. This solution was able to get 1000000 results.
• Ankur Anand: That was just awesome .. even though i'm having hard time understanding things there (no C++ background) i'm trying to figure it out what he has done !