"java.lang.Outofmemoryerror" error with List

Question

I have the following statement of the problem:

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 input is number 36, the method returns a list containing [2, 2, 3, 3].

• I called the method on 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)

Answer 1

Division is not being done by the right values here:

aux = x / i;

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

It should be instead:

aux = aux / i;

The numbers are also already placed in order so that the y it is not necessary.

Then the whole method could go 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;
}

Example in Ideone to confirm

Answer 2

Based on the Isac response, some improvements can be made:

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:

1. Use aux /= i.

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

3. Since the aux is divided, the upper limit of primes search is reduced.

4. No number aux has a divisor (other than itself) larger than its square root.

5. With the optimization of the square root, if the aux final is prime (or if the final x for primo) it ends up not being added to the list. O if in the end does it.

Like he said, the problem was you had the aux = x / i, that made him stay forever recalculating the same value and forever stuck in the noose. Except he was adding elements to the list until it exploded. Also, the variable y is not necessary.

Here is 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 way out:

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 working on ideone.