Return prime factors from int as input as an array

Question

I need to code an algorithm which takes an int, gets its prime factors, puts them into an array and returns them.

My code is the following.

public static int[] primfaktorzerlegung(int zahl) {
   int d=1; //this is the length of the array

   int[] result = new int[d]; //array has to be returned

   List<Integer> factors = new ArrayList<Integer>();

   for(int factor = 2; factor <= zahl; factor++) {
       while(zahl % factor == 0) {
           factors.add(factor);
           zahl = zahl / factor;
       }
   }

   for(int i : factors){ //trying to get every number of the arraylist
       int z = i;          
       result[d] = z; //trying to put the numbers of the arraylist into the array result
       d++;           //makes the array dimension one higher
   }
   return result; //returns the array

}

I get the following error:

Error: java.lang.ArrayIndexOutOfBoundsException:
Index 1 out of bounds for length 1
at: result[d] = z;

What could be the cause?

Answer 1

You are not actually increasing the size of the array by incrementing d. Once you have allocated the array, its size is fixed.

You can do this instead:

public static int[] primes(int number) {
    List<Integer> factors = new ArrayList<>();
    for(int factor = 2; factor <= number; factor++) {
        while (number % factor == 0) {
            factors.add(factor);
            number = number / factor;
        }
    }
    return factors.stream().mapToInt(n -> n.intValue()).toArray();
}

The stream() method exposes the ArrayList as a Stream, which allows you do use nice methods to manipulate collections. One of them is mapToInt, which allows you do apply a function to each element in the stream. You apply the function that takes an n and returns whatever comes in the body (the part after the ->). In particular, since you are putting together a collection of boxed Integers, you have to unbox them into ints (more on boxing here). The intValue() method does exactly that. Finally, you return an int[] by calling toArray() on it. In practice, you are saying: apply intValue() to each item in the list and return the resulting array.

Note that I took your main logic as is, I didn't go into the correctness of how you are computing prime factors.