如何降低此代码的复杂性，因为我收到错误：线程"main" java.lang.OutOfMemory中的异常错误：Java 堆空间

Question

我试图解决一个问题"给定一个偶数(大于2)，返回两个素数，其总和等于给定的数字"，并得到上述错误。错误是由于代码的复杂性，这是很清楚的。请提出任何降低复杂性的方法

我的代码是:

 public ArrayList<Integer> primesum(int A) {
         ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i=0;i<=A;i++)
        {
            //All the numbers are prime
            arr.add(1);
        }
        arr.set(0,0);//
        arr.set(1,0);
        for(int i=2; i<=Math.sqrt(A);i++)
        {
            if(arr.get(i)==1)
            for(int j=2;i*j<=A;j++)
            {
             arr.set(i*j,0);   
            }
        }
        for(int i=0;i<=Math.sqrt(A);i++)
        {
            if(arr.get(i)==1)
            {
                boolean b = checkprime((A-i));
                if(b)
                {
                    arr.clear();
                    arr.add(i);
                    arr.add(A-i);
                    break;
                }
            }
        }
        return arr;
    }
    private static boolean checkprime(int p)
    {
        boolean k =true;
        if(p==1)
        return false;
        for(int i=2;i<=Math.sqrt(p);i++)
        {
            if(p%i==0)
              k=false;
        }
        return k;
    }

Answer 1

算法的第一步构建了一个包含所有Integer到A的列表，这个列表可能非常大。包装器类效率很低，每个Integer占用16字节，更不用说List占用的空间了。既然您知道这个列表的大小，我建议使用int数组，代码如下:

public int[] primesum(int A) {
    int[] arr = new int[A + 1];
    for (int i = 0; i <= A; i++) {
        // All the numbers are prime
        arr[i] = 1;
    }
    arr[0] = 0;//
    arr[1] = 0;
    for (int i = 2; i <= Math.sqrt(A); i++) {
        if (arr[i] == 1)
            for (int j = 2; i * j <= A; j++) {
                arr[i * j] = 0;
            }
    }
    for (int i = 0; i <= Math.sqrt(A); i++) {
        if (arr[i] == 1) {
            boolean b = checkprime((A - i));
            if (b) {
                arr = new int[2];
                arr[0] = i;
                arr[1] = A - i;
                break;
            }
        }
    }
    return arr;
}
private static boolean checkprime(int p) {
    boolean k = true;
    if (p == 1)
        return false;
    for (int i = 2; i <= Math.sqrt(p); i++) {
        if (p % i == 0)
            k = false;
    }
    return k;
}

(如果A的值非常大，仍然有可能出现堆错误，但在这个版本中，它们至少在数组声明后立即发生。为了进一步优化，恐怕你需要重新考虑你的算法，不需要那个数组，当然，正如olambert所说，你可以随时调整堆空间的大小，使其适合。

Answer 2

您可以增加java应用程序的堆大小，这将允许您在内存耗尽之前处理更大的数据集。您可以在运行程序时通过使用-Xms和-Xmx标志来指定应用程序的堆大小。例如:

java -Xmx1G myProgram

将运行"myProgram"，最大堆大小为1GB。您可以通过运行命令

获取有关jvm参数的更多信息:

java -X

当然，如果你需要解决大整数的问题，你可能会发现你需要使用更有效的算法，使用更少的内存。

Answer 3

下面的算法使用Eratosthenes筛法生成小于给定数的所有素数，然后检查它们的和是否等于给定数并返回有效对。这种方法完全避免了使用checkPrime()方法:

public static void main(String[] args) {
    // TODO Auto-generated method stub
    int n = 120;
    int[] chk = new int[n];
    chk[0]=1;
    chk[1]=1;
    for(int i=2;i<n;i++) {
        if(chk[i]!=1){
            chk[i]=-1;
        }
        if(chk[i]==1) {
            continue;
        } else {
            for(int j=2;j*i<n;j++){
                chk[j*i]=1;
            }
        }
    }
    for(int i=2;i<n/2;i++) {
        if(chk[i]==-1) {
            if(chk[n-i]==-1) {
                System.out.println(i+"+"+(n-i));
            }
        }
    }
}

o/p

7+113
11+109
13+107
17+103
19+101
23+97
31+89
37+83
41+79
47+73
53+67
59+61

希望有帮助。您可以在找到一个匹配对后抛出一个break来跳过循环。(我还没有完全检查的角落案例，所以可能有一些问题的代码，但希望它得到的想法跨越)