How to reduce the complexity of this code as I am getting error :Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

Question

我正在尝试解决问题 "Given an even number ( greater than 2 ), return two prime numbers whose sum will be equal to given number." 并遇到上述错误。错误是由于代码复杂性造成的，这一点很明显。请提出任何降低复杂性的方法

我的代码是：

 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

您可以增加 java 应用程序的堆大小，这样您就可以在运行内存不足之前处理更大的数据集。当您运行您的程序时，您可以通过使用 -Xms 和 -Xmx 标志来指定应用程序的堆大小。例如：

java -Xmx1G myProgram

将运行 "myProgram" 的最大堆大小为 1GB。您可以获得有关可以通过运行ning:

指定的 jvm 参数的更多信息

java -X

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

Answer 2

以下算法使用埃拉托色尼筛法生成所有小于给定数的素数，然后检查它们的和是否等于给定数和 returns 个有效对。这种方法完全避免使用 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

希望对您有所帮助。找到一对匹配后，您可以插入一个 break 以跳过循环。（我还没有完全检查极端情况，因此代码可能存在一些问题，但希望它能理解这个想法）

Answer 3

您算法的第一步是构建一个包含所有 Integer 到 A 的列表，该列表可能非常大。包装器类效率很低，每个 Integer 占用 16 个字节，更不用说 space 和 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 所说，您总是可以调整堆的大小 space 以使其适合。）

How to reduce the complexity of this code as I am getting error :Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

How to reduce the complexity of this code as I am getting error :Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

java

generics

dynamic