java - HackerEarth 问题 : 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.

这是我编写的代码，它在 Eclipse 中输出 Out Of Memory 错误。

由于内存要求是 256 MB，我设置了 -Xmx256M，但是因为它给我一个 Out Of Memory 错误，我一定是误解了问题或者我的代码是内存使用方面的错误。我在这里做错了什么？我正在为较小的 lONGMAX 获得所需的输出，例如 10000 或 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

有两种可能:

• 您使用 -Xmx256M这意味着一个 256 MB 的堆。但不仅仅是堆，您的 VM 在尝试获取更多堆时可能会被杀死。

• 您为 VM 分配了 256 MB，但您的程序需要更多空间并被终止。 <----正如 RealSkeptic 所说，情况就是如此。

为了获得 1M 个素数，您需要调查一些 <100M 个数 (*)。因此，对于工作在 100_000_000 以下的主要筛子，它应该可以工作。这样筛子也适用于反转的数字。通过跳过偶数，您只需要 50 MB，因此您可以将限制设置为 100M。

通过使用位而不是字节，您可以将使用的内存减少 8 倍。您可以通过忽略以偶数开头的数字将其减少 2 倍，但这会变得复杂。

---

(*) 这是您可以在提交前轻松试用的内容。