CMPS 144L Lab Activity
Prime Factorize, Recursively

Definition: A number is prime if (and only if) it is a positive integer having exactly two (distinct) positive integer divisors, 1 and itself. (This excludes negative numbers, as well as 1, which has only itself as a divisor.)

If n = p₁ × p₂ × ··· × p_m, where each p_i is prime and p₁ ≤ p₂ ≤ ··· ≤ p_m, then we say that the list [p₁, p₂, ..., p_m] is the prime factorization of n.

The Fundamental Theorem of Arithmetic says that every positive integer has a unique prime factorization.

For this lab activity, you are charged with the task of developing a recursive Java method —found in the Java application PrimeFactorize— that produces the prime factorization of a given number. Here is that method, but with its body needing to be refined from pseudocode to Java code:

/* This recursive method produces a LinkedList containing the prime ** factorization of its first argument, n, under the assumption that n ** has no prime factors less than its second argument, k. ** pre: 2≤k≤n ∧ n % m ≠ 0 for all m in the range [2..k) */ private static LinkedList<Integer> primeFactorizationOfAux(int n, int k) { Repeatedly increment k until such time as either it is a divisor of n or it can be determined that n is prime. If n is prime, set result to the one-element list [n]. (Initially, make it the empty list, but then use the addFirst() method to insert n.) Otherwise, set result to the prime factorization of n/k, which can be computed recursively. (Note that the prime factorization of n/k has no factors less than k.) Then use addFirst() to insert k at the head of the list. }

Regarding how to create and use an instance of the java.util.LinkedList class, for our purposes all you will need are statements of the form

result = new LinkedList<Integer>() (which creates an empty list (capable of holding Integers) and assigns it to result), and
result.addFirst(k) (which places the value of k at the beginning of the list referred to by result.

The application repeatedly prompts the user to enter a positive integer, and for each one entered, it displays the prime factorization. Execution terminates when the user enters a value of 1 or less.

The actual output of the program is more extensive, as the recursive method that you are to complete is set up to narrate its own execution. Below is an example of a dialog between a user and the program:

Enter a positive integer (1 or less to quit): 450 Received n:450 and k:2 Received n:225 and k:2 Received n:75 and k:3 Received n:25 and k:3 Received n:5 and k:5 Having received n:5 and k:5, returning [5] Having received n:25 and k:3, returning [5, 5] Having received n:75 and k:3, returning [3, 5, 5] Having received n:225 and k:2, returning [3, 3, 5, 5] Having received n:450 and k:2, returning [2, 3, 3, 5, 5] Prime factorization: [2, 3, 3, 5, 5] Enter a positive integer (1 or less to quit): 10450 Received n:10450 and k:2 Received n:5225 and k:2 Received n:1045 and k:5 Received n:209 and k:5 Received n:19 and k:11 Having received n:19 and k:11, returning [19] Having received n:209 and k:5, returning [11, 19] Having received n:1045 and k:5, returning [5, 11, 19] Having received n:5225 and k:2, returning [5, 5, 11, 19] Having received n:10450 and k:2, returning [2, 5, 5, 11, 19] Prime factorization: [2, 5, 5, 11, 19] Enter a positive integer (1 or less to quit): 1 Goodbye.