-1

I am trying to solve a problem "Given an even number ( greater than 2 ), return two prime numbers whose sum will be equal to given number." and getting the above error. Error is due to code complexity which is clear. Please suggest any way to reduce complexity

My code is:

 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;
    }
jain28
  • 137
  • 5
  • 3
    You're adding too many things to your list... thus the "out of memory" error. – Jashaszun Aug 18 '15 at 17:49
  • Add more memory to Java with the `-Xmx` command-line argument – Andreas Aug 18 '15 at 17:55
  • possible duplicate of [What is an OutOfMemoryError and how do I debug and fix it](http://stackoverflow.com/questions/24510188/what-is-an-outofmemoryerror-and-how-do-i-debug-and-fix-it) – Raedwald Aug 18 '15 at 19:33

3 Answers3

0

You can increase the heap size of your java application which will allow you to process a larger set of data before running out of memory. You can specify the heap size for your application by using -Xms and -Xmx flags when you run your program. For example:

java -Xmx1G myProgram

would run "myProgram" with a maximum heap size of 1GB. You can get more information about jvm arguments you can specify by running:

java -X

Of course you may find that you need to use a more efficient algorithm which uses less memory if you need to solve the problem for large integers.

olambert
  • 1,075
  • 2
  • 7
  • 10
0

The following algorithm uses Sieve of Eratosthenes for generating all prime numbers lesser than the given number and then checks if their sum equals the given number and returns valid pairs. This approach spares the use of checkPrime() method altogether:

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

Hope that helps. You can throw in a break to skip loop after one matching pair is found.(I haven't quite checked the corner cases so there might be some issues with the code but hope it gets the idea across)

digidude
  • 289
  • 1
  • 8
0

The first step in your algorithm constructs a list of all Integers up to A, which could potentially be very large. The wrapper classes are quite inefficient, each Integer takes 16 bytes, not to mention the space the List takes. Since you know the size of this list, I'd suggest using an int array instead, with code something like:

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;
}

(It's still possible to get heap errors with very large values of A, but with this version they at least happen as soon as the array is declared. To optimize further I'm afraid you'd need to rethink your algorithm to not need that array, although of course as olambert says, you could always resize your heap space to make it fit.)

hugh
  • 2,237
  • 1
  • 12
  • 25