HackerEarth 问题的内存不足错误：反向素数

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

您实际上应该用列表替换您的布尔值[]，因为内存不足可能来自此 table。你没有使用最好的策略，因为你正在为每一个长期存在的人积累所有的价值。你最好只记住素数，试着重新思考素数的定义，并进行迭代推导。

Answer 2

有两种可能：

您使用 -Xmx256M 这意味着 256 MB 堆。但是，不仅仅是堆，您的虚拟机在尝试获取更多堆时可能会被杀死。
您为 VM 提供了 256 MB，但您的程序需要更多空间并被终止。 <---- 正如 RealSkeptic 所说，情况就是这样。

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

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

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

Answer 3

您声明：

final static long lONGMAX=1000000000000000L;

然后当你分配你的布尔数组时，你计算这个：

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

根据该定义，limit 将是 1,382,236,159。那是 1.3Gb，假设一个布尔值占用一个字节。您可能认为 VM 只为每个布尔值分配一位，但事实并非如此。

考虑改用 java.util.BitSet。

HackerEarth 问题的内存不足错误：反向素数

Out Of Memory error with HackerEarth Problem: Reverse Primes

java

optimization

out-of-memory

primes