Error "java.lang.OutOfMemoryError" with List

Question

Error "java.lang.OutOfMemoryError" with List

Navigation

#1 by (2 votes)
#2 by (2 votes)

1

I have the following problem statement:

A method that takes an integer as a parameter and returns a list of integers with their decomposed prime factors. As an example, if the entry is number 36, the method returns a list containing [2, 2, 3, 3].

I called the method in MAIN: System.out.println(b(36));
Expected result: [2,2,3,3].

I was able to implement the following method:

public static List<Integer> b(int x){
   List<Integer> numeros = new ArrayList<Integer>();
   int aux = x, i = 2, y = 0;

    while (i <= x) {
        if((primo(i) == true) && aux % i == 0){
            aux = x / i;
            numeros.add(y, i);
            y++;
        } else {
            i++;
        }
    }        
    return numeros;
}

Error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:3210)
    at java.util.Arrays.copyOf(Arrays.java:3181)
    at java.util.ArrayList.grow(ArrayList.java:261)
    at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:235)
    at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:227)
    at java.util.ArrayList.add(ArrayList.java:475)
    at desafio6.Desafio6.b(Desafio6.java:54)
    at desafio6.Desafio6.main(Desafio6.java:14)
/Users/alissonfernando/Library/Caches/NetBeans/8.1/executor-snippets/run.xml:53: Java returned: 1
FALHA NA CONSTRUÇÃO (tempo total: 25 segundos)

java arraylist

asked by anonymous 03.09.2017 / 03:24

2 answers

2

The division is not being made by the right values, here:

aux = x / i;

That divides always by the original value and not by the last one. Dividing by the original the aux always stays in 18 (36/2) and never changes, generating an infinite list of equal values, which ends up in the memory error presenting.

It should instead be:

aux = aux / i;

Numbers are already placed in order so that y is not required.

So the whole method might look like this:

public static List<Integer> b(int x){
   List<Integer> numeros = new ArrayList<Integer>();
   int aux = x, i = 2; //sem y

   while (i <= x) {
        if(primo(i) && aux % i == 0){
            aux = aux / i; //divisão correta agora aqui, ou aux/=i para ficar curto
            numeros.add(i); //adição normal à lista
        } else {
            i++;
        }
   }

   return numeros;
}

Ideone example to confirm

03.09.2017 / 03:49

Change domain android project How to call the form inside another - Visual Studio

score 2 · Accepted Answer

Based on Isac's response, you can make some improvements:

public static List<Integer> fatorar(int x) {
   List<Integer> numeros = new ArrayList<Integer>();
   int aux = x, s = (int) Math.sqrt(x);

   for (int i = 2; i <= s; i++) {
        if (primo(i)) {
            while (aux % i == 0) {
                aux /= i;
                s = (int) Math.sqrt(aux);
                numeros.add(i);
            }
        }
   }

   if (aux != 1 || numeros.isEmpty()) numeros.add(aux);
   return numeros;
}

The improvements are:

Use aux /= i .

Avoid checking more than once if the same number is prime.

Since aux is split, the upper limit of cousin fetching decreases.

No number% aux has divider (than himself) greater than its square root.

With the optimization of the square root, the aux % Quarter is a prime (or himself x for cousin) he ends up not being added to the list. The if at the end does this.

As he said, the problem was you have aux = x / i , which made him stay forever recalculating the same value and forever stuck in the loop. Except that he was adding elements on the list until it exploded. Also, the y variable is not required.

Here's the test:

public static void main(String[] args) {
    System.out.println("36: " + fatorar(36));
    System.out.println("60: " + fatorar(60));
    System.out.println("120: " + fatorar(120));
    System.out.println("144: " + fatorar(144));
    System.out.println("97: " + fatorar(97));
    System.out.println("128: " + fatorar(128));
    System.out.println("15: " + fatorar(15));
    System.out.println("2: " + fatorar(2));
    System.out.println("7: " + fatorar(7));
    System.out.println("1: " + fatorar(1));
    System.out.println("0: " + fatorar(0));
}

Here's the output:

36: [2, 2, 3, 3]
60: [2, 2, 3, 5]
120: [2, 2, 2, 3, 5]
144: [2, 2, 2, 2, 3, 3]
97: [97]
128: [2, 2, 2, 2, 2, 2, 2]
15: [3, 5]
2: [2]
7: [7]
1: [1]
0: [0]

see here running in ideone.