Out Of Memory error with HackerEarth Problem: 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.

Here is the code I've written which is giving me output Out Of Memory error in Eclipse.

Since memory requirement is 256 MB, I set -Xmx256M, but since it's giving me an Out Of Memory error, I must have misunderstood the question or my code is buggy in terms of memory utilization. What am I doing wrong here? I'm getting the desired output for smaller lONGMAX like 10000 or 1000000.

public class ReversePrime {
    final static long lONGMAX=1000000000000000L;
    final static int MAXLISTSIZE=1000000;
    final static boolean[] isPrime=isPrime();
    public static void main(String...strings ){

        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 revrse= reversePrime(prime);
                if ( (!(prime==revrse)) && (!reversedCheckedPrime.contains(revrse)) && 
                        (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 % 10;
            prime = prime / 10;
            result = result * 10 + rem ;
        }
        return result;
    }
    private static boolean[] isPrime() {
        int root=(int) Math.sqrt(lONGMAX)+1;
        root = root/2-1;
        int limit= (int) ((lONGMAX-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;
    }
}

Hackerearth Link

Answer 1

There are two possibilities:

• You use -Xmx256M which means a 256 MB heap. But there's more than just the heap and your VM may get killed when it tries to get more.

• You give 256 MB to your VM but your program needs more and gets killed. <---- As RealSkeptic says, this is the case.

In order to get 1M primes, you need to investigate some <100M numbers(*). So with a prime sieve working below 100_000_000, it should work. This way the sieve works for the reversed number as well. By skipping the evens, you need only 50 MB, so you can set the limit to maybe 100M.

You could reduce the memory used by a factor 8 by using bits instead of bytes. You could reduce it by a factor of 2 by ignoring numbers starting with an even digit, but this gets complicated.

---

(*) This is something you can easily try out before submitting.

Answer 2

You declare this:

final static long lONGMAX=1000000000000000L;

And then when you allocate your boolean array, you calculate this:

int limit= (int) ((lONGMAX-1)/2);

Based on that definition, limit will be 1,382,236,159. That's 1.3Gb, assuming a boolean takes one byte. You might be thinking that the VM only allocates one bit per boolean, but that's not how it works.

Consider using a java.util.BitSet instead.

Answer 3

You actually should replace your boolean[] with a List as the out of memory probably is coming from this table. You're not using the best strategy, as you're stacking all of the value for every long existing. You better should only keep in memory the prime numbers, try to rethink the definition of a prime number, and go on an iterative deduction.