Question

The prime factorization of a number is the unique list of prime numbers that, when multiplied, gives the number. For example, the prime factorization of 60 is 2 ∗ 2 ∗ 3 ∗ 5. In this problem you must write code to recursively find and return the prime factorization of the given number. You must print these in ascending sorted order with spaces in between.

For example, if your input is:

120

then you should print the following output:

2 2 2 3 5

Any solutions that do not use recursion will receive a grade of zero for all categories. (However, there are multiple good recursive solutions that exist for this problem.) Code for reading input and writing output has been provided in the Main class; your job is to complete the factorize() method. You may assume your input number is between 2 and 1,000, inclusive, and you may alter the starting code and/or use helper functions if you like.

//Starter code

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
  
// read input number (which will be between 2 and 1000)
int number = Integer.parseInt(sc.nextLine());
  
// factor the number into an array of prime factors
int[] factors = factorize(number);
  
// print array of factors
for (int i = 0; i < factors.length; i++) {
System.out.print(factors[i]);
if (i != factors.length - 1) {
System.out.print(" ");
}
}
System.out.println();
}
  
public static int[] factorize(int number) {
// TODO implement this
//throw new UnsupportedOperationException();
  
  //Use a recursive solution, thanks
}
}

Answer 1

import java.util.Scanner;

public class PrimeFactorization {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

// read input number (which will be between 2 and 1000)
        int number = Integer.parseInt(sc.nextLine());

// factor the number into an array of prime factors
        int[] factors = factorize(number);

// print array of factors
        for (int i = 0; i < factors.length; i++) {
            System.out.print(factors[i]);
            if (i != factors.length - 1) {
                System.out.print(" ");
            }
        }
        System.out.println();
    }

    public static int[] factorize(int number) {
        int n = number, count = 0;
        for (int i = 2; i <= number; i++) {
            while (n % i == 0) {
                ++count;
                n /= i;
            }
        }
        int[] arr = new int[count];
        int index = 0;
        n = number;
        for (int i = 2; i <= number; i++) {
            while (n % i == 0) {
                arr[index++] = i;
                n /= i;
            }
        }
        return arr;
    }
}